R+7
[Python] 그래프 문제, 어떻게 접근할 것인가 본문
분기 설정
알고리즘 문제 중 그래프가 나왔을 때, 우리가 생각해 볼 접근법을 설정한다면 다음과 같다.
1. 이동: 최단 거리나 최소 비용을 구하는가?
- 간선 비용이 모두 같음(또는 비용 없음): BFS
- 간선 비용이 다름
- 모두 양수: 다익스트라
- 음수 포함됨: 벨만-포드
- 한 지점이 아니라 '모든 지점 간'의 거리: 플로이드-워셜
2. 연결: 모든 노드를 하나로 묶거나 그룹화하는가?
- 최소 비용으로 전체를 하나로 연결: MST (크루스칼, 프림) 필수 조건: 무방향 그래프이어야 하며, 사이클이 없어야 함
- 같은 그룹/네트워크인지 확인하거나 두 그룹을 합침: 유니온-파인드 (얘는 여기 뿐 아니라 여러 군데 사용됨)
3. 작업의 선후 관계가 있거나 사이클을 찾아야 하는가?
- 순서 정하기, 선수 과목, 선행 조건: 위상 정렬 필수 조건: 방향 그래프이어야 하며, 사이클이 절대 없어야 함 (DAG)
- 사이클(순환) 존재 여부 판별:
- 무방향 그래프: 유니온-파인드
- 방향 그래프: DFS
알고리즘 별 설명
DFS
graph = []
visited = []
def dfs(now):
# 1. 현재 노드 방문 처리
visited[now] = True
# 2. 현재 노드와 인접한 노드를 확인
for nxt in graph[now]:
# 3. 아직 방문하지 않은 노드라면 더 깊이 들어감 (재귀)
if not visited[nxt]:
dfs(nxt)백트래킹
def backtracking(depth, path):
# 1. 종료 조건 (정답을 찾은 경우)
if depth == target_depth:
print(path)
return
# 2. 현재 단계에서 선택 가능한 후보들 탐색
for candidate in candidates:
# 3. 유망성 검사 (Constraint Check)
if is_promising(candidate):
# 4. 상태 변경 (선택)
visited[candidate] = True
path.append(candidate)
# 5. 다음 단계로 재귀 호출
backtracking(depth + 1, path)
# 6. 복구 (이게 백트래킹의 핵심!)
path.pop()
visited[candidate] = False플로이드 워셜
모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘. 거쳐가는 정점을 k로 설정하고, 이를 기준으로 기존 최단 거리와 비교해 갱신하는 것이 핵심이다.
V = 4
INF = int(1e9)
# 2차원 리스트(최단 거리 테이블)를 만들고, 모든 값을 무한으로 초기화
# 인덱스 편의를 위해 V + 1 크기로 할당
graph = [[INF] * (V + 1) for _ in range(V + 1)]
# 1. 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, V + 1):
for b in range(1, V + 1):
if a == b:
graph[a][b] = 0
# 2. 주어지는 간선 정보(가중치)로 초기화
# (중략)
# 3. 플로이드-워셜 알고리즘 수행 (핵심 로직)
# k: 거쳐가는 노드, i: 출발 노드, j: 도착 노드
for k in range(1, V + 1):
for i in range(1, V + 1):
for j in range(1, V + 1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])BFS
시작 정점으로부터 가까운 정점을 먼저 방문하는 순회. 가중치가 없는 그래프에서 최단 경로 찾을 경우 사용한다.
deque 사용과 방문 처리가 필수. 시간 복잡도는 모든 정점과 간선을 한 번씩 확인하므로 O(V+E)
from collections import deque
def bfs(start):
q = deque()
q.append(start)
visited = set()
visited.add(start_node)
while q:
now = queue.popleft()
for nxt in graph[now]:
if nxt not in visited:
q.append(nxt)
visited.add(nxt)플러드 필
최단 거리가 목적이 아니라 영역의 개수나 크기를 구하는 유형 (아래는 개수 구하는 유형)
count = 0
while q:
now = queue.popleft()
count += 1 # 한 칸씩 갈 때마다 카운트 증가
for nxt in graph[now]:
if nxt not in visited:
q.append(nxt)
visited.add(nxt)차원 확장
- 층을 구분하는 경우도 존재 - 2206 벽 부수고 이동하기
- 층을 나누다 못해 아예 차원을 비트마스킹으로 다루는 문제도 있다 - 1194 달이 차오른다, 가자
# 비트마스킹 비교 if not (keys & (1 << bit)):
가중치
- 가중치가 0 또는 1인 경우 구분이 필요하다면 → 가중치가 0인 노드는 앞으로, 가중치가 1인 노드는 뒤로 보내는 식.
popleft()와pop()이 동시에 가능하다는 점을 이용
여러 지점에서 동시에 번져나가는 상황
- BFS를 시작하기 전, 모든 시작점 좌표를 미리 큐에 전부 넣고 시작
시작점과 도착점이 정해져 있을 경우
- 시작점과 도착점에서 동시에 출발하는 양방향 BFS - 1525 퍼즐
- 경우의 수가 무지하게 많을 때 연산량을 줄이기 위해 사용
경로 복원이 필요할 경우 (역추적)
- 나를 여기로 보낸 직전 노드(parent)가 누군지 기록하는 배열을 만듦 (경로 리스트를 통째로 보내면 리스트 복사 비용 때문에 메모리와 시간이 초과될 가능성이 높음) - 13913 숨바꼭질 4
상태 변환
- 2차원 배열을 문자열이나 정수 하나로 압축해 관리하는 기법
- 2차원 좌표
y, x→i = y*cols + x
- 2차원 좌표
다익스트라
하나의 출발 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘. 매번 가장 비용이 적은 노드를 선택해 인접 노드의 최단 거리를 갱신하는 Greedy 방식을 사용한다. 우선순위 큐(heapq)를 활용하고, 모든 간선 가중치가 양수일 때 사용해야 한다.
import heapq
# 노드의 개수(V)와 간선의 개수(E)
V = 6
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for i in range(V + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (V + 1)
# 간선 정보 입력 예시 (출발 노드, 도착 노드, 가중치)
# graph[1].append((2, 2)) # 1번 노드에서 2번 노드로 가는 비용이 2
# graph[1].append((3, 5))
# graph[1].append((4, 1))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
# heapq는 튜플의 첫 번째 원소를 기준으로 최소 힙을 구성하므로 (거리, 노드) 순서로 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 큐에서 꺼낸 거리값이 테이블에 기록된 값보다 크다면 이미 처리된 적이 있는 노드이므로 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 1번 노드에서 시작
# dijkstra(1)벨만-포드
다익스트라와 동일하지만 간선 가중치가 음수일 때도 사용이 가능하다. 매 단계마다 그래프의 모든 간선을 전부 확인해 최단 거리를 갱신하는 특징이 있으며, 이를 통해 음수 사이클 존재 여부를 판별할 수 있다. (이 경우 예외 처리) 아무래도 매 라운드마다 모든 간선을 확인하기 때문에 시간 복잡도가 높은 편.
# 노드의 개수(V)와 간선의 개수(E)
V = 5
E = 6
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (V + 1)
# 간선 정보 입력 예시 (출발 노드, 도착 노드, 가중치)
# edges.append((1, 2, -1))
# edges.append((1, 3, 4))
# ... (문제 조건에 맞게 입력받아 세팅)
def bellman_ford(start):
# 시작 노드 초기화
distance[start] = 0
# 전체 V - 1번의 라운드(round)를 반복, 마지막 V번째는 음수 사이클 확인용
for i in range(V):
# 매 반복마다 모든 간선을 확인
for j in range(E):
cur_node = edges[j][0]
next_node = edges[j][1]
edge_cost = edges[j][2]
# 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
distance[next_node] = distance[cur_node] + edge_cost
# V번째 라운드에서도 값이 갱신된다면 음수 사이클이 존재한다는 의미
if i == V - 1:
return True # 음수 사이클 존재
return False # 정상 종료 (음수 사이클 없음)
# 1번 노드에서 시작
# has_negative_cycle = bellman_ford(1)유니온 파인드
여러 노드가 존재할 경우 두 노드가 서로 같은 집합에 속해 있는지 판별하거나, 두 그래프를 하나로 병합하는 서로소 집합 알고리즘. 특정 노드가 속한 집합의 대표 노드를 찾고(find), 이를 합함(union). 경로 압축이 필수적이다.
# 노드의 개수(V)
V = 6
# 부모 테이블 초기화 (처음에는 모든 노드가 자기 자신을 부모로 가짐)
parent = [0] * (V + 1)
for i in range(1, V + 1):
parent[i] = i
# Find 연산: 특정 원소가 속한 집합(루트 노드)을 찾기
def find_parent(parent, x):
# 자기 자신이 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
# 경로 압축(Path Compression) 기법: 찾은 루트 노드를 현재 노드의 부모로 바로 갱신
parent[x] = find_parent(parent, parent[x])
return parent[x]
# Union 연산: 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
# 번호가 더 작은 노드를 부모로 설정 (일반적인 갱신 규칙)
if a < b:
parent[b] = a
else:
parent[a] = b
# 연산 수행 예시
# union_parent(parent, 1, 4)
# union_parent(parent, 2, 3)
# union_parent(parent, 2, 4)
# 1번 노드와 3번 노드가 같은 집합인지 확인
# if find_parent(parent, 1) == find_parent(parent, 3):
# print("같은 집합입니다.")
# else:
# print("다른 집합입니다.")MST (최소 신장 트리)
그래프 내 모든 정점을 연결하는 부분 그래프 중 사용된 간선 가중치 합이 가장 작은 트리. 조건 상 모든 노드가 연결되어 있어야 하며, 사이클이 없어야 한다.
간선이 적은 희소 그래프의 경우 전체 간선을 비용 순 오름차순 정리 후 유니온-파인드로 사이클을 피해가며 간선을 선택하는 크루스칼이 있고, 간선이 많은 밀집 그래프의 경우 임의 시작 정점에서 출발해 현재 트리와 인접한 간선 중 우선순위 큐를 이용해 최소 비용 간선을 선택 확장하는 프림 기법이 존재.
크루스칼
import sys
# 유니온 파인드: 경로 압축(Path Compression) 적용
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
root_a = find(parent, a)
root_b = find(parent, b)
if root_a != root_b:
parent[root_b] = root_a
return True
return False
def kruskal(v, edges):
# 1. 간선을 가중치 기준으로 오름차순 정렬
edges.sort(key=lambda x: x[2])
parent = [i for i in range(v + 1)]
mst_weight = 0
edges_count = 0
for u, v, weight in edges:
# 2. 사이클이 생기지 않는다면 간선 선택
if union(u, v):
mst_weight += weight
edges_count += 1
# 정점 - 1개의 간선을 찾으면 종료 (최적화)
if edges_count == v - 1:
break
return mst_weight프림
import heapq
def prim(start_node, v, adj):
visited = [False] * (v + 1)
# (가중치, 정점) 형태로 우선순위 큐 관리
pq = [(0, start_node)]
mst_weight = 0
count = 0
while pq:
weight, curr = heapq.heappop(pq)
# 이미 방문한 정점이면 무시 (사이클 방지)
if visited[curr]:
continue
visited[curr] = True
mst_weight += weight
count += 1
if count == v: # 모든 정점을 방문했다면 종료
break
# 인접한 정점 중 방문하지 않은 곳을 큐에 삽입
for next_node, next_weight in adj[curr]:
if not visited[next_node]:
heapq.heappush(pq, (next_weight, next_node))
return mst_weight