yeolyi.com성열의 컴퓨터공학

그래프 탐색

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

배열은 앞에서부터 한 칸씩 훑으면 모든 값을 들를 수 있습니다. 하지만 그래프에는 “다음 칸”이 없습니다. 지하철 노선도의 한 역에서 갈 수 있는 역을 모두 둘러보려면 어떤 순서로 가야 할까요? 길이 돌고 돌아 들른 정점으로 다시 이어지기도 하니, 들른 곳을 표시하지 않으면 끝없이 맴돌 수도 있습니다.

기다리는 목록

그래프의 정점을 빠짐없이 둘러보는 일을 그래프 탐색(graph traversal)이라 합니다. 방문할 정점을 목록에 적어 두고 하나씩 꺼내 갑니다.

  1. 출발점을 목록에 넣는다.
  2. 목록에서 정점 하나를 꺼낸다. 이미 방문한 정점이면 건너뛴다.
  3. 방문했다고 표시하고, 아직 방문하지 않은 이웃을 목록에 넣는다.
  4. 목록이 비면 끝난다. 아니면 2로 돌아간다.

남은 질문은 목록에서 어떤 정점을 먼저 꺼낼까입니다. 큐를 쓰면 먼저 넣은 정점부터, 스택을 쓰면 나중에 넣은 정점부터 꺼냅니다.

ABCDEFGH
큐 (왼쪽이 앞, 앞에서 꺼냄)
A
방문 순서

출발점 A를 큐에 넣었습니다.

굵은 선은 각 정점을 처음 방문할 때 거쳐 온 간선입니다.

  1. 너비 우선으로 끝까지 진행해 봅시다.
  2. 깊이 우선으로 바꿔 다시 해 봅시다.
  3. 정점을 눌러 출발점을 바꿔 봅시다.

너비 우선과 깊이 우선

큐를 쓰는 방식을 너비 우선 탐색(breadth-first search, BFS)이라 합니다. 연못에 던진 돌의 물결처럼, 간선 1개 거리인 정점을 모두 방문한 뒤 2개, 3개 거리 순으로 넓혀 갑니다.

스택을 쓰는 방식은 깊이 우선 탐색(depth-first search, DFS)입니다. 방금 넣은 이웃을 바로 꺼내니 한쪽 길을 끝까지 들어갔다가, 막히면 가장 최근 갈림길로 돌아옵니다. 쌓였다가 거꾸로 풀리는 모양이 재귀와 같아서 재귀 함수로 짧게 쓰기도 합니다.

1#include <stdio.h>
2
3// 정점 A~H의 이웃
4char *neighbors[8] = {
5 "BC", "ADE", "AE", "BFG",
6 "BCF", "DEH", "DH", "FG",
7};
8// 방문했으면 1
9int visited[8];
10
11void dfs(char v) {
12 // v에 방문 표시
13 visited[v - 'A'] = 1;
14 printf("%c ", v);
15 // v의 이웃 w마다
16 char *p = neighbors[v - 'A'];
17 for (int i = 0; p[i] != '\0'; i++) {
18 char w = p[i];
19 if (visited[w - 'A'] == 0) {
20 // w에서 다시 깊이 들어간다
21 dfs(w);
22 }
23 }
24}
25
26int main(void) {
27 dfs('A');
28 printf("\n");
29 return 0;
30}

변수 없음
출력 없음

그래프는 위 데모와 같습니다. 재생하며 v를 봅시다. 막히면 함수가 끝나 직전 갈림길의 v로 돌아갑니다.

인접 리스트로 담으면 두 방식 모두 정점마다 한 번 방문하고 간선은 양 끝에서 한 번씩 살피니, 정점 수가 V, 간선 수가 E면 O(V + E)입니다.

미로의 최단 칸 수

너비 우선 탐색은 가까운 정점부터 방문하니, 처음 방문할 때 거쳐 온 길이 곧 간선이 가장 적은 길입니다. 미로도 칸을 정점으로, 맞닿은 칸을 간선으로 보면 그래프입니다.

출발 · 도착 · 칸의 숫자는 출발점에서 그 칸까지 온 칸 수입니다.

칸을 누르면 벽을 세우거나 허뭅니다.

너비 우선과 깊이 우선으로 각각 재생해 찾은 길의 길이를 비교해 봅시다.

깊이 우선 탐색은 처음 닿은 길에서 멈출 뿐, 가장 짧다는 보장이 없습니다. 가장 적은 걸음이 필요하면 너비 우선을, 백트래킹처럼 한 갈래를 끝까지 따라가 봐야 하는 문제라면 깊이 우선을 씁니다.

도전 문제

정점 6개가 서로 모두 간선으로 이어진 무방향 그래프에서 정점 A부터 깊이 우선 탐색을 합니다. 이웃을 살피는 순서는 아무렇게나 정해져 있습니다. 끝난 뒤 굵은 선(각 정점을 처음 방문할 때 거쳐 온 간선)만 따라 A에서 갈 때, 가장 먼 정점까지는 간선 몇 개를 지날까요? 숫자로 답하세요.