BFS와 DFS: 언제 하나만 사용할 수 있을까?

BFS와 DFS: 언제 하나만 사용할 수 있을까?

알고리즘을 공부하다 보면 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)가 모두 가능한 문제를 자주 접하게 됩니다. 하지만 일부 문제들은 BFS로만 풀어야 하거나, DFS로만 풀어야 하는 경우도 존재합니다.

이번 글에서는 "오직 BFS 또는 DFS로만 풀 수 있는 문제"를 정리해 보겠습니다.

---

1️⃣ BFS로만 풀 수 있는 문제 유형

BFS(너비 우선 탐색)는 최단 거리, 최단 횟수를 찾는 문제에서 반드시 사용됩니다.

이유는 BFS는 탐색을 진행할 때, 가까운 노드부터 차례대로 탐색하기 때문입니다.

✅ BFS로만 풀 수 있는 문제 유형

유형	설명
최단 거리 탐색	그래프에서 한 지점에서 다른 지점까지의 최소 이동 횟수를 구하는 문제
가중치가 없는 그래프에서 최단 경로	같은 깊이의 노드를 먼저 탐색하므로, 최단 경로를 보장
Flood Fill (물 채우기 문제)	특정 지점에서 시작해 모든 연결된 영역을 채워야 하는 문제
토마토 문제	BFS를 이용해 한 지점에서 여러 지점으로 동시에 확산하는 문제

---

📌 BFS로만 풀어야 하는 대표 문제

1. 최단 거리 문제 (백준 2178번 - 미로 탐색)

https://www.acmicpc.net/problem/2178

설명: N×M 크기의 미로에서 (1,1)에서 (N,M)까지 가는 최단 거리를 구하는 문제입니다.

이유: BFS는 한 번 방문한 곳을 다시 방문하지 않기 때문에, 처음 도착한 순간이 "최단 거리"임을 보장합니다.

➡ DFS는 깊이 우선 탐색이라 최단 거리를 보장하지 않음!

➡ 따라서 BFS를 반드시 사용해야 합니다. ✅

---

2. 다중 시작점에서 동시에 탐색해야 하는 문제 (백준 7576번 - 토마토 문제)

https://www.acmicpc.net/problem/7576

설명: 익은 토마토(1)가 익지 않은 토마토(0)로 확산하는데, 최소 며칠이 걸리는지 구하는 문제입니다.

이유: BFS는 한 번에 여러 개의 노드를 동시에 탐색하는 특성이 있어야 합니다.

➡ DFS로 탐색하면 "동시에 확산하는" 효과를 구현하기 어려움!

➡ BFS를 사용해야 모든 익은 토마토가 동시에 전파됨! ✅

---

2️⃣ DFS로만 풀 수 있는 문제 유형

DFS(깊이 우선 탐색)는 완전 탐색이 필요한 문제나, 한 번 갔던 곳을 다시 되돌아와야 하는 문제에서 필수적입니다.

(단, DFS는 완전 탐색이 필요한 문제에서 필수적이지만, BFS도 완전 탐색 문제를 해결할 수 있습니다.

✔ 다만, DFS는 깊이 우선으로 탐색해야 하는 경우에 적합하고, BFS는 최단 거리나 같은 깊이의 노드를 탐색해야 하는 문제에 적합합니다.)

✅ DFS로만 풀 수 있는 문제 유형

유형	설명
백트래킹(모든 경우의 수 탐색)	가능한 모든 조합을 탐색하는 문제
경로 찾기(한 번 이동한 곳을 되돌아갈 수 있는 문제)	미로에서 특정 조건을 만족하는 경로 찾기
연결 요소 개수 찾기	DFS로 한 덩어리(Connected Component)를 탐색
재귀적으로 해결하는 문제	그래프의 깊은 부분까지 탐색해야 하는 문제

 

---

📌 DFS로만 풀어야 하는 대표 문제

1. 모든 경로를 탐색하는 문제 (백준 1987번 - 알파벳 문제)

https://www.acmicpc.net/problem/1987

설명: N×M 보드에서 같은 알파벳을 두 번 방문하지 않도록 하면서, 최대로 이동할 수 있는 칸 수를 구하는 문제입니다.

이유: DFS를 사용해야 각 경로를 깊게 탐색하며 최적의 경로를 찾을 수 있습니다.

➡ BFS를 사용하면 한 경로에서 깊이 탐색할 수 없고, 모든 경로를 고려할 수 없음!

➡ DFS로 한 경로씩 탐색하며 최적 해를 찾는 방식이 필요함! ✅

---

2. 백트래킹이 필요한 문제 (N-Queen 문제)

https://www.acmicpc.net/problem/9663

설명: N×N 체스판에서 N개의 퀸을 서로 공격하지 않게 배치하는 문제입니다.

이유: DFS를 사용해야 "백트래킹(되돌아가기)"을 구현할 수 있습니다.

➡ BFS로는 "백트래킹"을 구현할 수 없기 때문에 DFS 필수! ✅

---

결론

DFS가 필수인 문제	BFS가 필수인 문제
백트래킹(모든 경우의 수 탐색)	최단 거리 문제
경로 탐색(특정 조건 만족)	여러 출발점에서 동시에 탐색
재귀적인 문제 해결	같은 깊이의 노드를 동시에 탐색해야 하는 문제