너비 우선 탐색과 깊이 우선 탐색 비교
[1]
/ \
[2] [3]
/ \ \
[4] [5] [6]
BFS (너비 우선): 1 → 2 → 3 → 4 → 5 → 6
DFS (깊이 우선): 1 → 2 → 4 → 5 → 3 → 6
| 구분 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 | 스택 (또는 재귀) |
| 탐색 순서 | 레벨별 | 깊이 우선 |
| 메모리 | O(w) 너비 | O(h) 높이 |
| 최단 경로 | 보장 | 보장 안 됨 |
| 활용 | 최단거리, 레벨순회 | 경로탐색, 사이클검출 |
Q.BFS와 DFS의 차이를 설명해주세요
넓게 먼저 보는지, 깊게 먼저 파는지가 다릅니다. 그 차이가 자료구조와 보장에서 나옵니다.
| 항목 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 | 스택 또는 재귀 |
| 방문 순서 | 가까운 곳부터 겹 단위로 | 한 갈래를 끝까지 |
| 최단 거리 | 보장한다 (간선 비용이 같을 때) | 보장하지 않는다 |
| 메모리 | 한 겹의 노드를 모두 담는다 | 경로 깊이만큼 담는다 |
| 잘 맞는 문제 | 최단 경로, 단계 수 세기 | 경로 존재 확인, 사이클 검출, 위상 정렬 |
메모리 특성이 실무에서 갈림길이 됩니다. 넓게 퍼지는 그래프(친구의 친구)는 BFS가 한 겹에서 수백만 노드를 담아 터질 수 있고, 깊은 그래프는 DFS가 스택을 넘길 수 있습니다.
흔한 실수: DFS로도 최단 경로를 구할 수 있다고 답하는 것. 모든 경로를 다 보면 구할 수는 있지만 그것은 완전 탐색이고, 처음 도달한 경로가 최단이라는 보장이 없습니다.
Q.최단 경로를 구할 때 BFS를 쓰는 이유는?
발견한 순서대로 방문하므로 처음 도달한 시점이 최단 거리가 되기 때문입니다.
| 겹 | 방문 대상 |
|---|---|
| 0 | 시작점 |
| 1 | 시작점에서 한 번에 갈 수 있는 곳 |
| 2 | 그곳에서 한 번에 갈 수 있는 곳 |
큐는 먼저 넣은 것을 먼저 꺼내므로 겹 1을 모두 처리한 뒤 겹 2로 넘어갑니다. 목표를 겹 k에서 처음 만났다면 그보다 짧은 경로는 이미 겹 1부터 k-1 까지에서 확인됐다는 뜻입니다.
단 전제가 있습니다. 모든 간선의 비용이 같아야 합니다. 비용이 다르면 간선 수가 적은 경로가 더 비쌀 수 있어 이 논리가 깨집니다. 그때는 다익스트라처럼 비용 순으로 꺼내는 알고리즘을 씁니다.
흔한 실수: 가중치 그래프에도 BFS를 쓰는 것. 지도의 도로처럼 거리가 다르면 BFS 결과는 최단 거리가 아니라 최소 환승 수에 가깝습니다.
Q.DFS를 스택으로 구현하는 방법은?
재귀가 쓰던 호출 스택을 직접 만듭니다.
스택에 시작 정점을 넣는다
스택이 빌 때까지
꺼낸다. 이미 방문했으면 건너뛴다
방문 표시하고 처리한다
이웃들을 스택에 넣는다
재귀와 방문 순서가 조금 다릅니다. 이웃을 넣는 순서의 역순으로 방문하므로, 재귀와 같은 순서를 원하면 이웃을 역순으로 넣습니다.
반복문으로 바꾸는 이유는 깊은 그래프에서 호출 스택이 넘치는 것을 막기 위해서입니다. 스택 영역은 보통 몇 MB로 제한되는데, 힙에 만든 스택은 훨씬 크게 쓸 수 있습니다. 정점 100만 개가 한 줄로 이어진 그래프라면 재귀는 터지고 반복문은 돕니다.
흔한 실수: 방문 표시를 넣을 때 하는 것. DFS는 꺼낼 때 표시해야 합니다. 넣을 때 표시하면 같은 정점을 여러 경로로 탐색해야 하는 문제(모든 경로 찾기)에서 답이 달라집니다.
먼저 스스로 답해보고 아래 답변과 견줘보세요. 막히는 부분은 문제로 확인할 수 있어요.