BFS vs DFS 정리
코테에서 그래프 탐색 문제는 대부분 두 가지 알고리즘으로 해결한다.
- DFS (Depth First Search)
- BFS (Breadth First Search)
처음 보면 두 알고리즘은
- directions 배열 사용
- 방문 체크
- 격자 이동
등의 같은 구조를 사용해서 거의 동일해 보여도 탐색 방식과 사용 목적은 완전히 다르다.
자꾸 헷갈리는 부분이 있어서 잊어버리지 않도록 정리하기로 했다!!
- DFS와 BFS의 차이
- 미로 문제에서 BFS를 사용하는 이유
- BFS 미로 최단거리 코드
- DFS로 최단거리를 구하지 않는 이유
1. DFS vs BFS 차이
DFS (Depth First Search)
DFS는 한 방향으로 끝까지 탐색한다.
예시
S → A → B → C → D막히면 다시 돌아와서 다른 길을 탐색한다.
이를 백트래킹(backtracking)이라 한다!!
특징
- 깊이 우선 탐색
- 일반적으로 재귀 사용
- 모든 경로 탐색에 적합
- 백트래킹 문제에 많이 사용
대표 문제
- 모든 경로 찾기
- 순열 / 조합
- 백트래킹
- 섬의 개수
BFS (Breadth First Search)
BFS는 가까운 것부터 탐색한다.
탐색 방식
거리 0
S
거리 1
A B
거리 2
C D E중심에서 바깥으로 퍼져나가는 구조!!
특징
- 너비 우선 탐색
- Queue 사용
- 최단거리 문제에 적합
대표 문제
- 미로 최단거리
- 바이러스 퍼짐
- 최소 이동 횟수
- 토마토 문제 (BOJ 7576)
2. 왜 미로 최단거리는 BFS인가
미로 문제의 목표는 보통 출발점 → 도착점 최단거리 구하기이다.
DFS는 먼 길을 먼저 발견할 수도 있다.
S → A → B → C → D → E 라는 경로를 탐색했을 때, 거리는 5
하지만 실제 최단 경로 S → X → E가 존재하고, 그 거리는 2
DFS는 모든 경로를 탐색해야만 최단거리를 알 수 있다.
반면 BFS는 거리가 가장 가까운 순서대로 탐색하는 방식이다.
그래서 처음 도착한 경로 = 항상 최단거리가 보장된다!!
3. BFS 미로 최단거리 코드
미로 예시
1 = 길
0 = 벽BFS 코드
function solution(maps){
// 미로의 세로 길이 (행 개수)
const n = maps.length;
// 미로의 가로 길이 (열 개수)
const m = maps[0].length;
// 상하좌우 이동을 위한 방향 배열
// [dx, dy] 형태로 이동 방향을 표현
const directions = [[0,1],[0,-1],[1,0],[-1,0]];
// BFS 탐색에 사용할 큐
// [x, y, dist] : 현재 위치와 시작점에서부터의 이동 거리
const queue = [[0,0,1]];
// 방문 여부를 기록하는 2차원 배열 생성
// 처음에는 모든 칸이 false (방문 안함)
const visited = Array.from({length:n},()=>Array(m).fill(false));
// 시작 위치 (0,0)은 이미 방문했으므로 true로 표시
visited[0][0] = true;
// queue에서 꺼낼 위치를 가리키는 포인터
// shift() 대신 사용하여 시간복잡도 증가를 방지
let head = 0;
// 큐에 탐색할 위치가 남아있는 동안 계속 BFS 탐색
while(head < queue.length){
// 현재 탐색할 위치를 큐에서 꺼냄
// queue[head]를 읽은 뒤 head를 증가시키는 후위 증가 연산
const [x,y,dist] = queue[head++];
// 현재 위치가 목표 위치라면
// 지금까지 이동한 거리 dist를 반환
if(x === n-1 && y === m-1) return dist;
// 현재 위치에서 상하좌우 4방향 탐색
for(const [dx,dy] of directions){
// 다음에 이동할 위치 계산
const nx = x + dx;
const ny = y + dy;
// 다음 위치가
// 1️⃣ 미로 범위 안에 있고
// 2️⃣ 길(1)이며
// 3️⃣ 아직 방문하지 않았다면
if(
nx >= 0 &&
ny >= 0 &&
nx < n &&
ny < m &&
maps[nx][ny] === 1 &&
!visited[nx][ny]
){
// 해당 위치를 방문 처리
visited[nx][ny] = true;
// 다음 탐색 위치로 큐에 추가
// 거리는 한 칸 이동했으므로 +1
queue.push([nx,ny,dist+1]);
}
}
}
// BFS 탐색이 끝날 때까지 목표 지점에 도달하지 못했다면
// 갈 수 없는 경우이므로 -1 반환
return -1;
}코드 흐름을 정리해보면...
- 시작점을 queue에 넣기
- 시작점을 visited 처리
- queue에서 하나 꺼냄
- 꺼낸 위치가 목표 지점이라면 거리 반환
- 상하좌우 탐색
- 갈 수 있고 방문하지 않았다면
→ 꺼낸 위치 visited 처리
→ 갈 수 있는 위치 queue에 추가 - queue가 빌 때까지 반복
- 끝까지 못 찾으면 -1 반환
4. DFS로 최단거리를 구하지 않는 이유
모든 경로를 탐색하고 각 경로의 길이를 기록한 뒤 가장 짧은 경로 선택하는 방식으로 이론적으로는 가능하다. 하지만 DFS는 가능한 경로의 수가 많아질수록 탐색량이 기하급수적으로 증가한다는 단점이 있다.
반면 BFS는 시작점에서 가까운 위치부터 탐색을 진행하기 때문에 도착점을 처음 발견하는 순간 그 경로가 최단거리가 된다. 또한 각 칸을 한 번씩만 방문하므로 시간복잡도는 O(n × m) 수준이다.
따라서 100 * 100 = 10,000번의 탐색만으로 최단거리를 구할 수 있어 BFS가 훨씬 효율적이다.
코딩테스트 알고리즘 선택 기준
| 문제 유형 | 알고리즘 |
|---|---|
| 미로 최단거리 | BFS |
| 퍼지는 문제 (불, 토마토, 바이러스) | BFS |
| 최소 이동 횟수 | BFS |
| 모든 경로 탐색 | DFS |
| 백트래킹 | DFS |
| 그래프 연결 요소 | DFS / BFS |
