그래프 탐색: BFS와 DFS

1736년 레온하르트 오일러는 쾨니히스베르크의 다리 일곱 개를 한 번씩만 건너는 산책길이 없음을 보였고, 그래프 이론은 이 답에서 시작했습니다.

점과 선

그래프는 정점(또는 노드)이라는 점들과, 그 점들을 잇는 간선이라는 선으로 이루어집니다. 생각은 간단한데 들어맞는 곳이 아주 많습니다. 도로로 이어진 도시, 링크로 이어진 웹 페이지, 친구 관계로 이어진 사람들, 벽이 없는 곳으로 이어진 미로의 칸들이 모두 그래프입니다. 문제를 그래프로 그려 놓으면 「여기서 저기로 갈 수 있을까?」 「가장 짧은 길은?」 같은 질문에 같은 몇 가지 알고리즘으로 답할 수 있습니다.

코드로 그래프 담기

그래프를 담는 흔한 방법은 인접 리스트입니다. 정점마다 이웃 목록을 적어 둡니다. MIT 6.006 강의 노트도 바로 이 방식으로, Adj[u]에 u와 이어진 정점들을 적은 배열이나 사전 Adj를 씁니다. 위 그래프는 이렇게 됩니다.

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

너비 우선 탐색: 한 겹씩

너비 우선 탐색(BFS)은 출발점 둘레를 한 겹씩 넓혀 가며 그래프를 탐색합니다. 먼저 거리 0인 출발점 자신, 다음에 거리 1인 이웃 전부, 그다음에 그 옆의 새 정점들인 거리 2, 이렇게 나아갑니다. 이를 위해 먼저 들어온 것이 먼저 나가는 줄인 큐를 씁니다. 큐 맨 앞의 정점을 꺼내 방문하고, 아직 못 본 이웃을 큐 뒤에 붙입니다. 예시에서 A부터 시작하면 BFS는 A, 그다음 B와 C, 그다음 D와 E, 마지막으로 F를 방문합니다. 바깥으로 한 겹씩 나아가므로 BFS가 어떤 정점에 처음 닿았을 때는 간선 수가 가장 적은 길을 찾은 것입니다. F는 A에서 간선 3개 떨어져 있고, 예를 들면 A, B, D, F입니다.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // first in, first out
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

깊이 우선 탐색: 갈 수 있는 데까지 가고 되돌아오기

깊이 우선 탐색(DFS)은 미로에서 한 손을 벽에 대고 걷는 사람처럼 움직입니다. 한 길을 갈 수 있는 데까지 깊이 따라갑니다. 막다른 곳이나 이미 본 곳에 닿으면 가장 최근 갈림길로 되돌아가 다음 길을 시도합니다. 큐 대신 나중에 들어간 것이 먼저 나오는 스택을 쓰며, 호출 스택이 기억을 대신해 주는 재귀로 쓰면 아주 자연스럽습니다. A부터 재귀 DFS를 하면 A, B, D, C, E, F 순서로 방문합니다. DFS도 BFS가 닿는 정점에 모두 닿지만, 따라간 길이 가장 짧은 길이라는 보장은 없습니다.

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // A B D C E F
}

언제 무엇을 쓸까

실험실의 첫 미로에서 BFS는 105칸을 방문하고 가능한 가장 짧은 22번 이동의 길을 찾습니다. DFS는 마침 목표 쪽으로 파고들어 31칸만 방문하지만, 찾은 길은 28번 움직이는 길입니다. 어느 쪽이 늘 덜 일하는 것은 아닙니다. 둘 다 정점과 간선을 정해진 횟수만큼만 다루므로, 정점 V개와 간선 E개인 그래프에서 둘 다 O(V + E) 시간이 걸립니다. 가장 적은 단계가 필요하면 BFS를 고릅니다. 퍼즐의 가장 적은 수, 두 사람 사이의 가장 적은 연결 같은 경우입니다. 모두 둘러보거나 선택을 끝까지 따라가야 하면 DFS를 고릅니다. 미로의 모든 방이 이어져 있는지 확인하거나, 퍼즐의 수를 한 줄씩 시도하다 막히면 되돌아오는 경우입니다. 도로처럼 간선마다 길이가 다르면 둘 다 그대로는 모자라고, 다익스트라 알고리즘 같은 방법이 BFS의 생각에 거리를 더해 씁니다.