GM 오락실
← 개인 공부 · Algorithm
STUDY NOTE · 개념 정리

BFS vs DFS 정리: 동작 방식, 구현, 시간 복잡도, 문제 유형별 선택

Algorithm
그래프의 모든 정점을 방문하는 두 가지 방법이다. BFS(너비 우선)는 큐로 가까운 정점부터 층층이 퍼져 나가 가중치 없는 그래프의 최단 거리를 구한다. DFS(깊이 우선)는 스택이나 재귀로 한 경로를 끝까지 파고든 뒤 되돌아와 경로 탐색, 백트래킹, 사이클 탐지에 쓴다. 둘 다 인접 리스트 기준 O(V + E)다.

1. 한눈에 비교

구분BFSDFS
자료구조큐스택 (또는 재귀 호출 스택)
탐색 순서시작점에서 가까운 정점부터 거리 순한 방향으로 끝까지 간 뒤 되돌아옴
최단 거리 (가중치 없음)보장보장 안 함
메모리한 층의 정점을 모두 큐에 담음 (넓은 그래프에서 큼)현재 경로 깊이만큼 (깊은 그래프에서 큼)
주 용도최단 거리, 최소 이동 횟수, 레벨 단위 처리모든 경로·조합 탐색, 백트래킹, 사이클 탐지, 위상 정렬, 연결 요소
주의방문 표시를 넣을 때 해야 중복이 없음재귀가 깊으면 스택 오버플로

2. 그래프 표현과 복잡도

표현공간두 정점 연결 확인모든 이웃 순회BFS/DFS 전체적합
인접 행렬O(V²)O(1)O(V)O(V²)정점이 적고 간선이 많을 때
인접 리스트O(V + E)O(차수)O(차수)O(V + E)대부분의 경우

격자(2차원 배열) 문제는 각 칸이 정점이고 상하좌우가 간선인 그래프다. 칸이 N×M개면 O(NM)이다.

3. BFS 동작 과정

1
/ \
2 3
/ \ \
4 5 6

BFS: 1 → 2 → 3 → 4 → 5 → 6 (거리 0, 1, 1, 2, 2, 2)
DFS: 1 → 2 → 4 → 5 → 3 → 6 (왼쪽 자식부터 방문할 때)
  1. 시작 정점을 큐에 넣고 방문 표시를 한다.
  2. 큐에서 하나를 꺼낸다.
  3. 꺼낸 정점의 이웃 중 방문하지 않은 정점을 방문 표시하고 큐에 넣는다.
  4. 큐가 빌 때까지 2~3을 반복한다.

큐는 먼저 넣은 것이 먼저 나오므로 거리 1인 정점을 모두 처리한 뒤에야 거리 2인 정점이 나온다. 그래서 어떤 정점에 처음 도달한 순간의 거리가 곧 최단 거리다.

4. BFS 구현: 격자 최단 거리

int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};

// map[r][c] == 1 이면 지나갈 수 있는 칸
int shortest(int[][] map, int n, int m) {
int[][] dist = new int[n][m];
for (int[] row : dist) Arrays.fill(row, -1); // -1: 미방문

ArrayDeque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0, 0});
dist[0][0] = 0;

while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = cur[0] + dr[d], nc = cur[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
if (map[nr][nc] == 0 || dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[cur[0]][cur[1]] + 1; // 넣을 때 방문 표시
queue.offer(new int[]{nr, nc});
}
}
return dist[n - 1][m - 1]; // 도달 못 하면 -1
}

방문 표시를 큐에서 꺼낼 때 하면, 아직 처리되지 않은 같은 칸이 여러 번 큐에 들어가 시간과 메모리가 크게 늘어난다. 넣는 순간 표시하는 것이 정석이다.

5. DFS 구현: 재귀와 명시적 스택

// 재귀
void dfs(int v) {
visited[v] = true;
for (int next : graph.get(v)) {
if (!visited[next]) dfs(next);
}
}

// 명시적 스택 (깊이가 매우 클 때)
void dfsIterative(int start) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int v = stack.pop();
if (visited[v]) continue;
visited[v] = true;
for (int next : graph.get(v)) {
if (!visited[next]) stack.push(next);
}
}
}

자바의 기본 스레드 스택은 재귀 깊이 수만 단계에서 StackOverflowError가 날 수 있다. 정점이 수십만 개인 일자형 그래프라면 명시적 스택으로 바꾼다. 명시적 스택 버전은 이웃을 넣는 순서 때문에 재귀 버전과 방문 순서가 다를 수 있다.

6. 문제 유형별 선택

문제 유형선택이유
최소 이동 횟수, 최단 거리 (모든 간선 비용이 같음)BFS처음 도달한 거리가 최단
연결 요소 개수 (섬의 개수)둘 다 가능모든 정점을 한 번씩 방문하면 됨
모든 경로·조합·순열 탐색DFS (백트래킹)한 경로를 끝까지 가 보고 되돌아오는 구조가 자연스러움
사이클 탐지 (방향 그래프)DFS현재 재귀 경로에 있는 정점을 다시 만나면 사이클
위상 정렬DFS 또는 BFS(진입 차수, Kahn 알고리즘)선후 관계 순서 정하기
간선마다 비용이 다름다익스트라BFS의 "처음 도달 = 최단"이 성립하지 않음
간선 비용이 0 또는 10-1 BFS (덱 사용)비용 0은 앞에, 1은 뒤에 넣음

7. 실제로 어떻게 적용되나

  1. 카테고리·메뉴 트리: 부모-자식 관계로 저장된 카테고리를 화면에 펼칠 때 DFS(재귀)로 순회하면 들여쓰기 순서 그대로 나온다. DB에서는 재귀 CTE(WITH RECURSIVE)로 같은 일을 한다.
  2. 작업 의존성 순서: 빌드 도구나 마이그레이션 스크립트가 "A가 끝나야 B 실행" 관계를 풀 때 위상 정렬을 쓴다. 순환 의존이 있으면 정렬이 불가능하다는 것도 함께 검출된다.
  3. N단계 관계 찾기: "친구의 친구까지"처럼 거리 제한이 있는 관계는 BFS로 거리 k까지만 확장한다.

8. 면접 질문으로 정리

  1. Q. BFS와 DFS의 차이는? BFS는 큐를 써서 가까운 정점부터 넓게 탐색하고, DFS는 스택이나 재귀로 한 경로를 깊게 탐색한 뒤 되돌아온다. 둘 다 인접 리스트에서 O(V + E)다.
  2. Q. 최단 거리는 왜 BFS로 구하나? BFS는 거리 순서대로 정점을 방문하므로 처음 도달한 시점의 거리가 최단 거리다. 단, 모든 간선의 비용이 같을 때만 성립한다.
  3. Q. 가중치가 있으면? BFS로는 안 되고 다익스트라(음수 간선이 없을 때)나 벨만-포드(음수 간선이 있을 때)를 쓴다.
  4. Q. BFS에서 방문 표시는 언제 해야 하나? 큐에 넣을 때 해야 같은 정점이 여러 번 들어가는 것을 막을 수 있다.
  5. Q. DFS를 재귀로 구현할 때 주의점은? 그래프가 깊으면 호출 스택이 넘쳐 StackOverflowError가 날 수 있다. 이때는 명시적 스택으로 바꾼다.
Gunmo Lee
since 2021.07
BFS vs DFS 정리: 동작 방식, 구현, 시간 복잡도, 문제 유형별 선택 | GM 오락실