BFS와 DFS — 언제 무엇을 써야 하는가
개요
알고리즘 스터디에서 여러 유형의 문제를 풀면서 "코드는 돌아가는데 왜 이렇게 짜는지 모르겠다"는 경험이 이 글의 출발점이었습니다.
이 글에서는 BFS와 DFS 각각의 핵심 구조를 정리하고, 기본 패턴에서 심화 문제(최단 경로, 경로 존재 여부)까지 단계적으로 다룹니다. 단순한 개념 나열이 아니라, 코드를 작성하면서 실제로 막혔던 부분과 그 이유를 중심으로 정리했습니다.
| 구분 | BFS | DFS |
|---|---|---|
| 자료구조 | Queue (FIFO) | Stack / 재귀 (LIFO) |
| 탐색 방향 | 레벨 순서 (너비 우선) | 깊이 우선 (한 방향 끝까지) |
| visited 추가 타이밍 | 큐에 넣기 직전 | 노드 방문 시 |
| 적합한 상황 | 최단 경로, 레벨별 처리 | 경로 존재 여부, 전체 순회 |
| 시간복잡도 | O(V + E) | O(V + E) |
| 공간복잡도 | O(V) | O(V) |
BFS 너비 우선 탐색
Queue를 사용하는 이유
BFS의 핵심은 먼저 발견한 노드를 먼저 처리하는 것입니다. Queue는 FIFO(First In, First Out) 구조이기 때문에, 시작 노드와 가까운 노드들을 먼저 넣고 먼저 꺼냅니다. 이 특성 덕분에 레벨 순서 탐색이 자연스럽게 보장됩니다. Stack을 쓰면 가장 나중에 넣은 노드를 먼저 꺼내게 되어 깊이 우선이 되어버립니다.
시작 노드: 1
그래프: 1 → [2, 3], 2 → [4], 3 → [5]
Queue 흐름:
[1] → poll(1), offer(2,3) → [2, 3]
[2, 3] → poll(2), offer(4) → [3, 4]
[3, 4] → poll(3), offer(5) → [4, 5]
...
탐색 순서: 1 → 2 → 3 → 4 → 5 (레벨 순서 보장)기본 패턴
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next : graph[cur]) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
}
}
}visited를 큐에 넣기 직전에 표시하는 것이 핵심입니다. 꺼낼 때 표시하면 같은 노드가 큐에 중복으로 들어간 뒤에야 걸러집니다.
그래프 최단 경로
기본 BFS 패턴을 익히고 나서 처음 맞닥뜨린 심화 문제가 그래프에서 두 노드 사이의 최단 경로를 구하는 것이었습니다.
기본 패턴과 다른 점이 딱 하나 있습니다. 큐에 노드만 넣는 게 아니라, 거리 정보도 함께 들고 다녀야 한다는 것입니다.
queue.offer(new int[]{start, 0}); // {노드, 현재까지의 거리}int[]로 묶어서 넣는 이유는, 노드를 꺼낼 때마다 "이 노드까지 몇 칸 왔는지"를 같이 알아야 하기 때문입니다. 거리를 별도 변수로 관리하면 큐에서 꺼낸 노드와 거리가 엇갈릴 수 있어서, 묶어서 함께 이동시키는 것이 안전합니다.
visited 추가 타이밍
기본 패턴과 마찬가지로, visited는 큐에 넣기 직전에 표시해야 합니다. 꺼낼 때 표시하면 같은 노드가 큐에 중복으로 들어갈 수 있습니다.
// ❌ 꺼낼 때 추가하면 늦다
int[] current = queue.poll();
visited.add(current[0]); // 이미 큐에 중복으로 들어간 후일 수 있음
// ✅ 넣기 직전에 추가해야 한다
visited.add(neighbor);
queue.offer(new int[]{neighbor, distance + 1});전체 코드
int shortestPath(Map<Integer, List<Integer>> graph, int start, int end) {
if (start == end) return 0;
Queue<int[]> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(new int[]{start, 0});
visited.add(start);
while (!queue.isEmpty()) {
int[] current = queue.poll();
int node = current[0];
int distance = current[1];
for (int neighbor : graph.getOrDefault(node, Collections.emptyList())) {
if (visited.contains(neighbor)) continue;
if (neighbor == end) {
return distance + 1;
}
visited.add(neighbor);
queue.offer(new int[]{neighbor, distance + 1});
}
}
return -1;
}start 노드를 큐에 넣기 직전에 visited.add(start)로 표시하고, 이후 neighbor도 offer 직전에 visited 처리를 합니다. 목적지에 도달했을 때는 현재 노드까지의 거리에 1을 더한 distance + 1을 반환합니다. getOrDefault를 사용하면 인접 노드가 없는 경우에도 NPE 없이 안전하게 처리할 수 있습니다.
2D 그리드 최단 경로
그래프 최단 경로를 이해하고 나서 만난 것이 2D 그리드 버전이었습니다. 노드 번호 대신 (row, col) 좌표로 위치를 표현한다는 점만 다르고, 핵심 구조는 동일합니다.
int[]를 HashSet에 쓰면 안 되는 이유
처음 막혔던 부분이 바로 이것이었습니다.
// ❌ 이렇게 하면 안 된다
Set<int[]> visited = new HashSet<>();
visited.contains(new int[]{row, col}); // 항상 false — 참조를 비교하기 때문
// ✅ 이렇게 해야 한다
Set<String> visited = new HashSet<>();
visited.contains(row + "," + col); // 문자열은 내용 비교int[]는 HashSet에서 내용이 아니라 참조(주소) 를 비교합니다. new int[]{1, 2}를 두 번 만들면 서로 다른 객체로 인식되기 때문에, "1,2" 문자열 키로 바꿔야 정상적으로 동작합니다.
상하좌우 이동을 directions 배열로 추상화한 이유
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};4방향 이동 로직을 반복문 하나로 처리할 수 있고, 대각선 이동이 추가되는 경우에도 배열에 {-1, -1} 등을 추가하기만 하면 되어 확장이 쉽습니다.
경계 조건 체크 순서
범위 초과 → visited → 벽 순서를 지켜야 ArrayIndexOutOfBoundsException 없이 안전하게 처리됩니다. 범위를 먼저 확인하지 않으면 배열 인덱스 접근 자체가 터집니다.
if (newRow < 0 || newRow >= grid.length || newCol < 0 || newCol >= grid[0].length) continue;
if (visited.contains(newRow + "," + newCol)) continue;
if (grid[newRow][newCol] == wall) continue;전체 코드
int shortestGridPath(int[][] grid, int[] start, int[] end) {
int[][] directions = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
if (start[0] == end[0] && start[1] == end[1]) return 0;
int wall = 1;
Queue<int[]> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(new int[]{0, start[0], start[1]});
visited.add(start[0] + "," + start[1]);
while (!queue.isEmpty()) {
int[] current = queue.poll();
int distance = current[0];
int row = current[1];
int col = current[2];
for (int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow < 0 || newRow >= grid.length || newCol < 0 || newCol >= grid[0].length) continue;
if (visited.contains(newRow + "," + newCol)) continue;
if (grid[newRow][newCol] == wall) continue;
if (end[0] == newRow && end[1] == newCol) {
return distance + 1;
}
visited.add(newRow + "," + newCol);
queue.offer(new int[]{distance + 1, newRow, newCol});
}
}
return -1;
}그래프 최단 경로와 동일한 패턴입니다. start 좌표를 offer 직전에 visited 처리하고, 이후 neighbor 좌표도 offer 직전에 visited에 추가합니다.
DFS 깊이 우선 탐색
재귀를 사용하는 이유
DFS의 핵심은 한 방향으로 끝까지 탐색하고, 막히면 돌아오는 것입니다. 재귀는 이 구조와 자연스럽게 맞아떨어집니다. 함수가 자기 자신을 호출하면서 깊이 들어가고, 조건에 걸리면 호출 스택을 거슬러 올라오는 방식이 DFS의 탐색 흐름과 동일하기 때문입니다.
시작 노드: 0
그래프: 0 → [1, 2], 1 → [3], 2 → [4]
재귀 흐름:
dfs(0) → dfs(1) → dfs(3) → 막힘, 복귀
→ 복귀
→ dfs(2) → dfs(4) → 막힘, 복귀
→ 복귀
탐색 순서: 0 → 1 → 3 → 2 → 4 (깊이 우선)기본 패턴
boolean[] visited = new boolean[n];
void dfs(int node) {
visited[node] = true;
for (int next : graph[node]) {
if (!visited[next]) {
dfs(next);
}
}
}visited 없이 재귀를 돌리면, 사이클이 있는 그래프에서 무한루프에 빠집니다. visited는 선택이 아니라 필수입니다.
경로 존재 여부 판별
DFS 심화에서 다룬 문제는 그래프에서 source에서 destination까지 경로가 존재하는지 여부를 반환하는 것이었습니다.
특이한 점은 그래프가 int[][] edges, 즉 간선 목록 형태로 주어진다는 것입니다. 인접 리스트가 바로 주어지지 않기 때문에, 직접 구성해야 했습니다.
인접 리스트를 직접 구성하는 이유
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
if (!graph.containsKey(edge[0])) graph.put(edge[0], new ArrayList<>());
if (!graph.containsKey(edge[1])) graph.put(edge[1], new ArrayList<>());
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}양방향으로 넣는 이유는 무방향 그래프이기 때문입니다. A→B 간선이 있으면 B에서도 A로 갈 수 있어야 합니다. 한 방향만 넣으면 역방향 탐색이 불가능해집니다.
재귀 DFS의 체크 순서
처음에는 visited 체크를 먼저 써야 할 것 같았는데, 순서에 주의해야 합니다.
boolean dfs(Map<Integer, List<Integer>> graph, Set<Integer> visited, int current, int destination) {
if (current == destination) return true;
if (visited.contains(current)) return false;
visited.add(current);
...
}이 코드에서는 pathExists 메서드 상단에서 source == destination을 먼저 처리하기 때문에, dfs 함수 내부에서 이 케이스가 직접 발생하지는 않습니다. 그럼에도 destination 체크를 visited보다 먼저 두는 이유는 방어적 설계 때문입니다. 상위 호출부가 변경되거나 dfs 함수를 다른 문맥에서 재사용할 경우, visited가 먼저 오면 이미 방문한 destination에 대해 false를 반환할 수 있으므로 도달 여부를 항상 먼저 확인하는 것이 안전합니다.
전체 코드
boolean pathExists(int n, int[][] edges, int source, int destination) {
if (source >= n || destination >= n) return false;
if (source == destination) return true;
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
if (!graph.containsKey(edge[0])) graph.put(edge[0], new ArrayList<>());
if (!graph.containsKey(edge[1])) graph.put(edge[1], new ArrayList<>());
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
Set<Integer> visited = new HashSet<>();
return dfs(graph, visited, source, destination);
}
boolean dfs(Map<Integer, List<Integer>> graph, Set<Integer> visited, int current, int destination) {
if (current == destination) return true;
if (visited.contains(current)) return false;
visited.add(current);
for (int neighbor : graph.get(current)) {
if (dfs(graph, visited, neighbor, destination)) return true;
}
return false;
}BFS와 DFS 선택 기준
| 상황 | 선택 | 이유 |
|---|---|---|
| 두 노드 사이 최단 경로 | BFS | 레벨 순서로 탐색하므로 처음 도달한 경로가 최단 |
| 경로 존재 여부 확인 | DFS | 한 방향으로 끝까지 탐색하므로 존재 확인에 효율적 |
| 그래프 전체 순회 | DFS | 재귀로 자연스럽게 모든 노드 방문 가능 |
| 2D 그리드 탈출 경로 | BFS | 최단 이동 횟수가 필요하면 BFS |
| 레벨별 처리가 필요한 경우 | BFS | 큐 구조가 레벨 순서를 자동으로 보장 |
두 알고리즘의 시간복잡도는 O(V+E)로 동일합니다. 선택 기준은 속도가 아니라 문제가 요구하는 탐색 방향입니다.
공통 주의사항
visited는 선택이 아니라 필수
사이클이 있는 그래프에서 visited 없이 탐색하면 무한루프에 빠집니다. BFS는 큐에 넣기 직전, DFS는 노드 방문 시 반드시 표시해야 합니다.
엣지케이스 체크리스트
start == end(또는source == destination): 바로 0 또는 true 반환- 그래프가 비어있는 경우:
graph.get(node)가 null이면 NPE 발생 가능 - 2D 그리드: 범위 초과 → visited → 벽 순서로 체크
int[]를 HashSet 키로 쓰지 말 것
int[]는 참조를 비교하기 때문에 contains()가 의도대로 동작하지 않습니다. 2D 좌표는 "row,col" 문자열 키로 변환해서 사용해야 합니다.
면접에서 설명하는 법
코드를 짜는 것과 말로 설명하는 것은 다른 능력입니다. 면접에서 BFS/DFS 문제를 받으면, 코드보다 먼저 사고 과정을 말하는 연습을 해두면 좋습니다.
BFS를 설명한다면
"Queue를 사용합니다. 시작 노드를 넣고, 꺼낼 때마다 인접 노드를 추가합니다. visited를 관리해서 무한루프를 방지합니다. FIFO 구조 덕분에 먼저 발견한 노드를 먼저 처리하게 되어 레벨 순서 탐색이 보장됩니다."
DFS를 설명한다면
"재귀를 사용합니다. 한 방향으로 끝까지 탐색하고 돌아오는 구조입니다. visited 없이 구현하면 사이클에서 무한루프가 발생하기 때문에 반드시 관리해야 합니다."
선택 기준을 물어본다면
"최단 경로나 레벨별 처리가 필요하면 BFS, 경로 존재 여부나 전체 순회가 필요하면 DFS를 선택합니다. 두 알고리즘의 시간복잡도는 동일하게 O(V+E)이므로, 문제가 요구하는 탐색 방향으로 결정합니다."
