깊이 우선 탐색과 너비 우선 탐색
다음에 처리할 정점을 고르는 규칙만 다른 깊이 우선 탐색과 너비 우선 탐색을 같은 방향 그래프에서 손으로 추적하고, 방문 표시를 큐에 넣을 때 해야 하는 이유를 확인합니다. 너비 우선 탐색이 간선 수가 가장 적은 거리를 구하는 이유를 증명합니다.
미로를 빠짐없이 둘러보는 방법은 크게 두 가지입니다. 한 갈래를 끝까지 따라간 뒤 돌아와 다른 갈래로 가는 방법과, 입구에서 가까운 곳부터 한 겹씩 넓혀 가는 방법입니다. 그래프에서는 앞의 것을 깊이 우선 탐색(depth-first search, DFS), 뒤의 것을 너비 우선 탐색(breadth-first search, BFS)이라고 합니다.
이 글을 읽고 나면 다음을 할 수 있습니다.
- 인접 목록을 보고 두 탐색의 방문 순서와 큐의 상태를 손으로 적습니다.
- 너비 우선 탐색으로 간선 수가 가장 적은 거리를 구하고, 그것이 맞는 이유를 설명합니다.
- 방문 표시를 늦게 했을 때 생기는 중복 방문을 찾아 고칩니다.
첫 글의 인접 목록과 연결 성분, 앞 글의 가중치 그래프를 씁니다.
같은 그래프, 다른 방문 순서
방향 간선 A→B, A→C, B→D, C→D가 있는 그래프를 인접 목록으로 적으면 A: [B, C], B: [D], C: [D], D: []입니다. 두 탐색 모두 A에서 출발하고, 이웃은 목록에 적힌 순서대로 보며, 이미 방문한 정점은 다시 방문하지 않습니다. 두 탐색 모두 A 다음에 B를 방문합니다. 세 번째로 방문하는 정점은 각각 무엇일까요?
결과 확인하기
깊이 우선 탐색은 D, 너비 우선 탐색은 C입니다. 깊이 우선 탐색은 B에서 더 내려갈 수 있으면 내려가므로 순서가 A, B, D, C입니다. 너비 우선 탐색은 A에서 간선 하나로 닿는 B와 C를 먼저 끝내므로 A, B, C, D입니다.
같은 그래프에서 다음 처리 대상을 달리 고릅니다
A에서 출발해 이웃을 B, C 순서로 볼 때 DFS와 BFS가 정점을 방문하는 순서를 단계별로 나란히 비교합니다.
이산수학 · 연결과 계산
같은 그래프에서 다음 처리 대상을 달리 고릅니다
방향 간선 A→B, A→C, B→D, C→D를 이웃 순서 B,C로 읽으면 DFS는 A,B,D,C이고 BFS는 A,B,C,D입니다.
- 화살표: 방향 간선
D는 두 정점의 이웃이지만 한 번만 방문합니다. DFS는 B의 하위 탐색을 마친 뒤 C로, BFS는 같은 깊이 B·C를 먼저 처리합니다.
이 예의 조건
- 인접 목록은 A: [B, C], B: [D], C: [D], D: []이고, 이미 방문한 정점은 다시 방문하지 않습니다.
- 왼쪽 칸은 두 탐색의 방문 순서와 BFS의 queue이고, 오른쪽 칸은 그 단계에서 일어난 일입니다. 전체 도표의 글자는 아래 표에 모았습니다.
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| A 방문 두 탐색 모두 A에서 출발합니다. |
| |
| B 방문 첫 이웃 B를 방문합니다. |
|
|
| 세 번째 방문의 차이 DFS는 B 아래의 D로 내려가고, BFS는 먼저 발견한 C를 방문합니다. |
|
|
| 마지막 방문 남은 정점을 방문하고, 이미 방문한 D는 다시 처리하지 않습니다. |
|
|
같은 그래프에서 다음 처리 대상을 달리 고릅니다
A에서 출발해 이웃을 B, C 순서로 볼 때 DFS와 BFS가 정점을 방문하는 순서를 단계별로 나란히 비교합니다.
이산수학 · 연결과 계산
같은 그래프에서 다음 처리 대상을 달리 고릅니다
방향 간선 A→B, A→C, B→D, C→D를 이웃 순서 B,C로 읽으면 DFS는 A,B,D,C이고 BFS는 A,B,C,D입니다.
- 화살표: 방향 간선
D는 두 정점의 이웃이지만 한 번만 방문합니다. DFS는 B의 하위 탐색을 마친 뒤 C로, BFS는 같은 깊이 B·C를 먼저 처리합니다.
이 예의 조건
- 인접 목록은 A: [B, C], B: [D], C: [D], D: []이고, 이미 방문한 정점은 다시 방문하지 않습니다.
- 왼쪽 칸은 두 탐색의 방문 순서와 BFS의 queue이고, 오른쪽 칸은 그 단계에서 일어난 일입니다. 전체 도표의 글자는 아래 표에 모았습니다.
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| A 방문 두 탐색 모두 A에서 출발합니다. |
| |
| B 방문 첫 이웃 B를 방문합니다. |
|
|
| 세 번째 방문의 차이 DFS는 B 아래의 D로 내려가고, BFS는 먼저 발견한 C를 방문합니다. |
|
|
| 마지막 방문 남은 정점을 방문하고, 이미 방문한 D는 다시 처리하지 않습니다. |
|
|
도표는 두 순서를 단계별로 나란히 보여 줍니다. D는 B와 C 양쪽의 이웃이지만 두 탐색 모두 한 번만 방문합니다. BFS 옆에 적힌 queue는 너비 우선 탐색의 코드를 볼 때 설명합니다.
깊이 우선 탐색: 한 갈래를 끝까지
def dfs(graph, start):
seen, order = set(), []
def visit(v):
seen.add(v)
order.append(v)
for u in graph[v]:
if u not in seen:
visit(u)
visit(start)
return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(dfs(graph, "A"))['A', 'B', 'D', 'C']안쪽 함수 visit이 자기 자신을 부르는 재귀로 한 갈래를 끝까지 따라갑니다. visit("D")가 끝나면 그 호출을 부른 visit("B")로 돌아가고, B에 더 볼 이웃이 없으므로 다시 visit("A")로 돌아가 남은 이웃 C를 봅니다. 방문한 정점을 기억하는 집합 seen이 없으면 C에서 D를 한 번 더 방문하고, 사이클이 있는 그래프에서는 탐색이 끝나지 않습니다.
너비 우선 탐색: 큐에 넣을 때 표시한다
from collections import deque
def bfs(graph, start):
depth = {start: 0}
queue, order = deque([start]), []
while queue:
v = queue.popleft()
order.append(v)
for u in graph[v]:
if u not in depth:
depth[u] = depth[v] + 1
queue.append(u)
return order, depth
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
order, depth = bfs(graph, "A")
print(order)
print(depth)['A', 'B', 'C', 'D']
{'A': 0, 'B': 1, 'C': 1, 'D': 2}deque는 먼저 넣은 것을 먼저 꺼내는 큐입니다. 딕셔너리 depth는 방문 표시를 겸하면서 출발점에서 몇 간선 떨어졌는지를 적습니다. 정점을 하나 꺼내 처리할 때마다 큐는 [A], [B, C], [C, D], [D], [] 순서로 바뀝니다. B를 꺼냈을 때 D를 큐에 넣으면서 바로 depth에 적으므로, C를 꺼냈을 때는 D가 이미 표시되어 있어 다시 넣지 않습니다.
두 탐색 모두 정점마다 한 번씩 그 정점의 인접 목록을 훑습니다. 인접 목록의 길이를 모두 더하면 방향 그래프에서는 간선 수, 무방향 그래프에서는 차수의 합인 간선 수의 두 배이므로, 전체 시간은 입니다.
너비 우선 탐색의 깊이는 가장 적은 간선 수다
depth에 적히는 값은 출발점에서 그 정점까지 가는 경로의 간선 수 가운데 가장 작은 값입니다. 깊이가 d인 정점을 꺼낼 때 새로 발견한 이웃은 깊이 d + 1로 큐의 맨 뒤에 붙으므로, 큐에는 언제나 깊이가 d인 정점들 뒤에 깊이가 d + 1인 정점들이 이어서 들어 있습니다. 반복 내내 참으로 남는 이 불변식 때문에 정점은 깊이가 작은 것부터 차례로 꺼내집니다. 어떤 정점 v까지 간선 d개로 가는 경로가 있다면, 그 경로에서 v 바로 앞의 정점은 간선 d − 1개로 닿으므로 더 먼저 꺼내지고, 꺼내질 때 v를 발견합니다. 그래서 v는 깊이 d보다 늦게 발견될 수 없고, 처음 발견될 때 적힌 깊이가 가장 작은 간선 수입니다. 가중치가 없는 그래프의 최단 경로를 너비 우선 탐색으로 구하는 이유입니다.
깊이 우선 탐색에는 이런 성질이 없습니다. 대신 한 갈래를 끝까지 따라가므로 사이클을 찾거나 작업의 선후 순서를 정하는 데 자주 쓰입니다.
닿지 않는 정점과 연결 성분
두 함수는 출발점에서 닿을 수 있는 정점만 방문합니다. 예제에 E: []를 더해도 A에서 E로 가는 간선이 없으므로 결과는 그대로입니다. 무방향 그래프에서는 한 번의 탐색이 출발점의 연결 성분을 모두 방문하므로, 모든 정점을 방문했으면 연결 그래프입니다. 방문하지 않은 정점에서 탐색을 다시 시작한 횟수까지 세면 연결 성분의 개수가 됩니다. 스택과 큐로 구현하는 방법은 자료구조·알고리즘 교재의 스택과 깊이 우선 탐색 DFS와 큐와 너비 우선 탐색 BFS에서 다룹니다.
더 깊이: 너비 우선 탐색으로 이분 그래프 판정하기
첫 글에서 이분 그래프에는 홀수 길이의 사이클이 없다는 것을 보았습니다. 연결된 무방향 그래프에서는 그 반대도 성립합니다. 깊이가 짝수인 정점을 X, 홀수인 정점을 Y로 나눕니다. 간선으로 이어진 두 정점은 깊이가 많아야 1 차이 나므로(연습 문제 4번), 같은 쪽끼리 잇는 간선이 있다면 두 끝의 깊이가 같은 d입니다. 그러면 출발점에서 한쪽 끝까지 가는 d개의 간선, 그 간선, 다른 쪽 끝에서 돌아오는 d개의 간선이 길이 2d + 1인 닫힌 보행을 이룹니다.
길이가 홀수인 닫힌 보행에는 홀수 길이의 사이클이 들어 있습니다. 같은 정점이 두 번 나오면 그 자리에서 닫힌 보행 두 개로 나눌 수 있고, 길이의 합이 홀수이므로 둘 중 하나는 홀수이기 때문입니다. 그래서 홀수 사이클이 없는 그래프에서는 같은 쪽끼리 잇는 간선이 없고, X와 Y가 이분 그래프의 두 쪽이 됩니다.
정리
- 깊이 우선 탐색은 한 갈래를 끝까지 따라간 뒤 돌아오고, 너비 우선 탐색은 출발점에서 가까운 정점부터 한 겹씩 방문합니다. 같은 깊이 안의 순서는 인접 목록을 따릅니다.
- 방문 표시가 같은 정점을 두 번 처리하는 일을 막으며, 너비 우선 탐색에서는 큐에 넣을 때 표시합니다.
- 두 탐색은 출발점에서 닿을 수 있는 정점만 방문하고, 인접 목록을 쓰면 시간이 걸립니다.
- 너비 우선 탐색이 처음 발견할 때 적는 깊이는 간선 수가 가장 적은 거리이고, 깊이 우선 탐색이 처음 닿는 경로는 가장 짧지 않을 수 있습니다.
연습 문제
1. 이웃의 순서 바꾸기
A의 이웃 목록을 [C, B]로 바꾸면 dfs와 bfs의 방문 순서는 어떻게 되나요?
해설 보기
깊이 우선 탐색은 A에서 C로 먼저 내려가 D까지 간 뒤 돌아와 B를 방문하므로 A, C, D, B입니다. 너비 우선 탐색은 깊이 1인 정점을 C, B 순서로 처리한 뒤 D를 처리하므로 A, C, B, D입니다.
2. 방문 표시를 늦게 하면
bfs를 고쳐서 큐에서 꺼낼 때 방문 표시를 하고, 이미 표시된 정점을 꺼내면 건너뛰게 했습니다. 예제 그래프에서 D는 큐에 몇 번 들어가나요?
해설 보기
두 번입니다. B를 꺼낼 때도, C를 꺼낼 때도 D는 아직 큐에서 꺼내지 않아 표시되지 않았으므로 두 번 들어갑니다. 꺼낼 때 건너뛰는 검사가 있어 방문 순서는 A, B, C, D로 같지만, 이웃이 많은 그래프에서는 같은 정점이 큐에 이웃 수만큼 쌓일 수 있습니다.
3. 닿을 수 있는 정점
예제에 E: [A]를 더합니다. A에서 출발한 dfs와 E에서 출발한 dfs의 결과는 각각 무엇인가요? 본문의 어느 문장으로 판정했는지도 쓰세요.
해설 보기
A에서 출발하면 A, B, D, C로 그대로입니다. E→A는 E에서 나가는 간선이라 A에서 E로는 갈 수 없고, 탐색은 출발점에서 닿을 수 있는 정점만 방문하기 때문입니다. E에서 출발하면 E, A, B, D, C로 모든 정점을 방문합니다.
4. 이웃한 정점의 깊이 차이
무방향 그래프에서 간선 uv로 이어진 두 정점의 너비 우선 탐색 깊이는 많아야 1 차이 남을 증명하세요. 방향 그래프에서는 왜 성립하지 않는지도 예를 드세요.
해설 보기
본문에서 보았듯 깊이는 출발점에서 가는 경로의 가장 적은 간선 수입니다. u까지 간선 depth(u)개로 가는 경로 뒤에 간선 uv를 붙이면 v까지 간선 depth(u) + 1개로 가는 보행이므로 depth(v) ≤ depth(u) + 1입니다. 무방향 간선은 v에서 u로도 지날 수 있으므로, u와 v를 바꾸어 같은 논증을 하면 depth(u) ≤ depth(v) + 1입니다. 두 부등식을 합치면 차이는 많아야 1입니다. 방향 간선 A→B, B→C, C→A에서 A에서 출발하면 깊이가 A 0, B 1, C 2인데, 간선 C→A의 두 끝은 2 차이 납니다. C→A를 거꾸로 지날 수 없어 둘째 부등식이 나오지 않습니다.
꼭 있어야 하는 줄은 다음과 같습니다.
- 깊이가 가장 적은 간선 수라는 본문의 결과를 쓴다는 줄.
- u까지의 경로에 간선 uv를 붙여 얻은 depth(v) ≤ depth(u) + 1.
- 무방향이라 u와 v를 바꿀 수 있다는 줄과 반대쪽 부등식.
5. 틀린 증명 고치기
다음 논증에서 근거 없는 줄을 찾고, A: [B, D], B: [C], C: [D], D: []인 그래프로 반례를 보이세요.
주장: 깊이 우선 탐색이 어떤 정점에 처음 닿는 경로도 간선 수가 가장 적다.
증명: 방문 표시 때문에 각 정점은 한 번만 방문한다.
더 짧은 경로가 있었다면 탐색이 그 경로로 먼저 닿았을 것이다.
따라서 처음 닿은 경로가 가장 짧다.해설 보기
근거 없는 줄은 "그 경로로 먼저 닿았을 것이다"입니다. 너비 우선 탐색에서는 깊이가 작은 정점부터 꺼낸다는 불변식이 이 줄을 뒷받침하지만, 깊이 우선 탐색은 가까운 정점부터 방문하지 않습니다. 반례의 그래프에서 dfs는 A의 첫 이웃 B로 내려가 C를 거쳐 D에 닿으므로 처음 닿는 경로가 A → B → C → D로 간선 3개입니다. 그런데 A → D는 간선 1개입니다. bfs는 A를 꺼낼 때 B와 D를 함께 발견해 D의 깊이를 1로 적습니다.
꼭 있어야 하는 줄은 다음과 같습니다.
- 근거 없는 줄의 지적과, 너비 우선 탐색에서는 무엇이 그 줄을 뒷받침하는지.
- 반례에서 깊이 우선 탐색이 처음 닿는 경로와 그 간선 수.
- 더 짧은 경로 하나.
6. 종합 과제: 그래프 하나를 네 가지로 분석하기
이 과제는 장 실습: 그래프 하나를 네 가지로 분석하기에서 이어집니다. 시작 상태와 단계별 점검, 완성 파일과 풀이를 그 글에 모았습니다.
다음 글의 장 실습을 마친 뒤 다음 장으로 넘어갑니다.