그래프 탐색, 최단경로와 최소신장트리

1. BFS와 DFS

BFS

시작 정점에서 가까운 정점부터 레벨 순서로 방문하며 큐를 사용한다. 가중치가 없거나 모든 간선 가중치가 같은 그래프의 최단 간선 수를 구할 수 있다.

• 인접리스트 기준 O(V+E)
• 최단 거리, 연결 요소, 이분 그래프 판정 등에 사용

DFS

한 경로를 가능한 깊게 탐색한 뒤 되돌아오며 재귀 또는 스택을 사용한다.

• 인접리스트 기준 O(V+E)
• 사이클 판정, 위상정렬, 경로 탐색, 연결 요소 등에 사용

방문 순서는 인접 정점의 저장 순서에 따라 달라질 수 있으므로 문제에서 “작은 번호부터” 같은 조건을 확인해야 한다.

2. 위상정렬

방향 비순환 그래프(DAG)의 정점을 모든 간선 방향을 지키도록 일렬로 나열한다.

• 진입차수가 0인 정점을 큐에서 꺼내는 Kahn 방식
• DFS 종료 순서의 역순을 사용하는 방식
• 사이클이 있으면 모든 정점을 위상정렬할 수 없다.
• 결과가 하나로 유일하지 않을 수 있다.

3. 최단경로

* 음수 사이클이 없어야 정상적인 최단거리가 정의된다.

완화(relaxation)는 dist[v] > dist[u] + w(u,v)이면 더 짧은 값으로 갱신하는 연산이다.

4. 최소신장트리(MST)

연결된 가중 무방향 그래프의 모든 정점을 연결하면서 간선 가중치 합이 최소인 트리이다. 정점이 V개이면 간선은 V-1개이다.

Kruskal

간선을 가중치 순으로 정렬하고 사이클을 만들지 않는 간선을 선택한다. 사이클 여부는 Union-Find로 효율적으로 확인한다.

Prim

하나의 정점에서 시작해 현재 트리와 외부 정점을 연결하는 가장 작은 간선을 반복 선택한다. 우선순위 큐를 사용할 수 있다.

5. Union-Find

서로소 집합을 관리한다.

• find(x): x가 속한 집합의 대표를 찾는다.
• union(a,b): 두 집합을 합친다.
• 경로 압축과 랭크·크기 기준 합치기로 성능을 높인다.

6. BFS·DFS 의사코드와 방문 시점

BFS는 큐에 넣는 순간 방문 표시를 해야 같은 정점이 여러 번 큐에 들어가는 것을 막는다.

from collections import deque
q = deque([start])
visited[start] = True
while q:
    u = q.popleft()
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            dist[v] = dist[u] + 1
            q.append(v)

DFS는 재귀 진입 시 방문 표시한다. 재귀 스택의 색을 구분하면 방향 그래프의 back edge와 사이클을 판정할 수 있다.

7. 위상정렬 추적

Kahn 방식은 진입차수 0인 정점을 큐에 넣고 제거하면서 이웃 진입차수를 줄인다.

A → C ← B, C → D
초기 진입차수 0: A, B
가능한 순서: A,B,C,D 또는 B,A,C,D

처리한 정점 수가 V보다 작으면 사이클이 존재한다. 큐에서 어떤 정점을 먼저 꺼내는지에 따라 여러 결과가 나올 수 있다.

8. Dijkstra와 완화

pq = [(0, s)]
while pq:
    d, u = heappop(pq)
    if d != dist[u]:
        continue
    for v, w in adj[u]:
        nd = d + w
        if nd < dist[v]:
            dist[v] = nd
            heappush(pq, (nd, v))

우선순위 큐 구현은 보통 O((V+E) log V)이다. 음수 간선이 있으면 한 번 확정한 정점의 거리가 나중에 더 작아질 수 있어 탐욕적 확정이 안전하지 않다.

9. Bellman-Ford와 Floyd-Warshall

Bellman-Ford는 모든 간선을 V-1회 완화한다. 그 뒤 한 번 더 완화가 가능하면 시작점에서 도달 가능한 음수 사이클이 있다.

Floyd-Warshall의 상태는 “1..k번 정점만 중간 정점으로 허용했을 때 i에서 j까지 거리”이다.

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

시간 O(V³), 공간 O(V²)이며 모든 쌍 최단경로에 적합하다.

10. MST 선택 과정

Kruskal은 간선 중심, Prim은 정점 집합 확장 중심이다.

Kruskal: 간선 정렬 → 작은 간선부터 → 서로 다른 집합이면 채택
Prim: 임의 시작 → 현재 트리에서 밖으로 나가는 최소 간선 채택

MST는 모든 정점을 최소 총비용으로 연결한다. 특정 시작점에서 각 정점까지 거리를 최소화하는 최단경로 트리와 목적이 다르다.

11. Union-Find 최적화

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

경로 압축과 랭크/크기 합치기를 함께 쓰면 연산의 분할 상환 비용은 거의 상수인 O(α(n))이다.

12. 알고리즘 선택표

최종 확인 문제

1. BFS에서 정점을 큐에서 꺼낼 때가 아니라 넣을 때 방문 표시하는 이유를 설명하시오.
2. Kahn 위상정렬이 처리한 정점 수가 V보다 작을 때 무엇을 뜻하는가?
3. Dijkstra에 음수 간선을 허용할 수 없는 핵심 이유를 설명하시오.
4. Bellman-Ford에서 V-1회 완화 후 한 번 더 완화가 가능하면 무엇을 의미하는가?
5. 최단경로 트리와 최소신장트리의 목적 차이를 설명하시오.