DFS/BFS, 깊이 우선과 너비 우선의 차이 이해하기

 

한 길을 깊게 갈까, 가까운 곳부터 볼까?

이번에는 코딩테스트에서 자주 나오는 DFS/BFS를 공부했다.

미로 탐색, 연결 요소, 토마토, 최단 거리 문제를 풀기 전에 기본 개념을 먼저 정리해두려고 한다.
처음에는 DFS와 BFS가 둘 다 “탐색”이라 비슷하게 느껴졌는데, 공부해보니 핵심 차이는 생각보다 단순했다.

DFS = 한 길을 먼저 깊게 탐색한다
BFS = 가까운 곳부터 차례대로 탐색한다

다만 여기서 주의할 점이 있다.

DFS가 한 방향으로만 가고 끝나는 것은 아니다.
BFS가 진짜 동시에 모든 방향으로 움직이는 것도 아니다.

이 두 부분이 처음에 조금 헷갈려서 같이 정리해보려고 한다.

---

1. DFS와 BFS는 언제 사용할까?

DFS와 BFS는 보통 그래프나 2차원 배열에서 연결된 곳을 탐색할 때 사용한다.

예를 들면 이런 문제들이다.

문제 유형주로 사용하는 탐색

연결 요소 개수 구하기	DFS / BFS
섬의 개수 구하기	DFS / BFS
바이러스 전파	DFS / BFS
미로 최단 거리	BFS
토마토 익는 날짜	BFS
최단 거리 탐색	BFS
모든 경로 탐색	DFS
백트래킹	DFS

간단히 정리하면 이렇게 볼 수 있다.

연결된 덩어리를 찾는 문제 → DFS/BFS 둘 다 가능
최단 거리, 최소 이동 횟수 → BFS
모든 경우를 끝까지 탐색 → DFS

---

2. DFS란?

DFS는 Depth First Search, 즉 깊이 우선 탐색이다.

말 그대로 한 방향으로 갈 수 있는 데까지 먼저 들어간다.

DFS = 한 길을 먼저 깊게 들어가기

예를 들어 아래와 같은 그래프가 있다고 하자.

        1
      /   \
     2     3
     |     |
     4     5

1번에서 시작하면 DFS는 보통 이런 식으로 탐색할 수 있다.

1 → 2 → 4 → 3 → 5

먼저 1에서 2로 가고, 2에서 4까지 깊게 들어간다.
그런데 4에서는 더 이상 갈 곳이 없다.

그러면 탐색이 끝나는 것이 아니라, 다시 돌아온다.
그리고 아직 방문하지 않은 다른 방향인 3으로 간다.

---

3. DFS는 한 방향으로만 가는 걸까?

처음에 내가 헷갈렸던 부분이 바로 이거였다.

“DFS는 한 방향으로 깊게 간다”라고 하니까,
다른 방향은 안 보고 한쪽으로만 가는 건가 싶었다.

정확히는 그렇지 않다.

DFS는 다음과 같은 방식이다.

한 방향으로 갈 수 있는 데까지 먼저 가본 뒤,
더 이상 갈 수 없으면 다시 돌아와서
아직 방문하지 않은 다른 방향도 탐색하는 방식

즉, 한 방향만 보는 게 아니라 한 방향을 먼저 보는 것이다.

오해정확한 이해

DFS는 한 방향으로만 간다	한 방향을 먼저 끝까지 가본다
막히면 끝난다	막히면 이전 위치로 돌아온다
다른 방향은 안 본다	돌아와서 다른 방향도 본다

쉽게 말하면 미로에서 이런 느낌이다.

왼쪽 길을 끝까지 가본다.
막히면 다시 돌아온다.
아직 안 가본 오른쪽 길을 가본다.

그래서 DFS에는 되돌아오기, 즉 백트래킹의 느낌이 같이 들어간다.

---

4. DFS는 언제 떠올리면 좋을까?

DFS는 보통 “연결된 것을 끝까지 탐색”하거나 “모든 경우를 확인”해야 할 때 자주 사용한다.

문제 유형DFS를 떠올리는 이유

연결 요소	한 덩어리를 끝까지 방문 처리하기 좋음
섬의 개수	붙어 있는 땅을 모두 방문 처리
바이러스	연결된 컴퓨터를 따라 전파
모든 경로 탐색	한 경로를 끝까지 가보고 돌아옴
백트래킹	선택하고 들어갔다가 되돌아옴
조합/순열	가능한 경우를 깊게 탐색

문제에서 이런 느낌이 나오면 DFS를 생각해볼 수 있다.

연결된 영역을 모두 찾아라
가능한 모든 경우를 구해라
한 경로를 끝까지 확인해라

---

5. BFS란?

BFS는 Breadth First Search, 즉 너비 우선 탐색이다.

DFS가 한 길을 깊게 들어가는 방식이라면,
BFS는 현재 위치에서 가까운 곳부터 차례대로 확인한다.

BFS = 가까운 곳부터 넓게 탐색하기

같은 그래프를 다시 보자.

        1
      /   \
     2     3
     |     |
     4     5

1번에서 시작하면 BFS는 보통 이렇게 탐색한다.

1 → 2 → 3 → 4 → 5

먼저 1과 바로 연결된 2, 3을 확인한다.
그다음 2, 3과 연결된 4, 5를 확인한다.

즉, 한쪽으로 깊게 들어가는 것이 아니라 가까운 곳부터 한 단계씩 넓혀가는 방식이다.

---

6. BFS는 동시에 모든 방향으로 움직이는 걸까?

BFS도 처음에는 조금 헷갈렸다.

“가까운 곳부터 퍼져 나간다”라고 하니까,
진짜 동시에 모든 방향으로 움직이는 건가 싶었다.

하지만 실제 코드는 동시에 움직이지 않는다.

BFS는 Queue를 사용해서 하나씩 꺼내고 처리한다.

Queue에 시작점을 넣는다.
하나를 꺼낸다.
연결된 다음 위치들을 Queue에 넣는다.
다시 하나씩 꺼내며 반복한다.

예를 들어 1번에서 시작하고, 1번과 2, 3이 연결되어 있다면:

Queue: [1]

1을 꺼냄
2, 3을 Queue에 넣음

Queue: [2, 3]

2를 꺼냄
3을 꺼냄
...

즉, 실제 코드는 하나씩 처리한다.

다만 탐색 결과를 보면, 시작점에서 가까운 곳부터 한 겹씩 퍼져 나가기 때문에
마치 동시에 퍼지는 것처럼 보인다.

그래서 이렇게 이해하면 좋다.

BFS는 실제로 동시에 움직이는 것은 아니지만,
가까운 곳부터 한 층씩 퍼져 나가는 방식이다.

특히 토마토 문제, 불 확산 문제, 감염 전파 문제에서는 이 “퍼져 나가는 느낌”이 중요하다.

---

7. BFS는 언제 떠올리면 좋을까?

BFS는 보통 최단 거리나 최소 이동 횟수 문제에서 자주 사용한다.

문제 유형BFS를 떠올리는 이유

미로 최단 거리	가까운 칸부터 탐색하므로 최단 거리 보장
최소 이동 횟수	한 번 이동 비용이 같을 때 적합
토마토	하루 단위로 주변에 동시에 퍼짐
감염 확산	시간 단위로 주변으로 퍼짐
불/물 확산	한 단계씩 퍼지는 구조
레벨 탐색	1단계, 2단계, 3단계 순서로 탐색

문제에서 이런 표현이 나오면 BFS를 먼저 떠올리면 된다.

가장 짧은 거리
최소 몇 번
며칠 후
몇 단계 만에
동시에 퍼진다
가까운 곳부터

---

8. DFS와 BFS 비교

구분DFSBFS

탐색 방식	한 방향으로 깊게 탐색	가까운 곳부터 넓게 탐색
느낌	한 길을 끝까지 가보기	물결처럼 퍼져 나가기
사용하는 자료구조	재귀 / Stack	Queue
최단 거리	보장하지 않음	간선 비용이 같으면 보장
자주 쓰는 문제	연결 요소, 백트래킹, 모든 경로	미로, 토마토, 최단 거리
헷갈릴 점	한 방향만 보는 게 아님	실제로 동시에 움직이는 건 아님

---

9. 예시 문제로 이해하기

다음 그래프에서 1번부터 시작해 모든 위치를 방문한다고 해보자.

        1
      /   \
     2     3
     |     |
     4     5

연결 관계는 다음과 같다.

위치이동할 수 있는 곳

1	2, 3
2	1, 4
3	1, 5
4	2
5	3

---

10. DFS로 탐색하면

DFS는 한 길을 깊게 먼저 탐색한다.

1 → 2 → 4 → 3 → 5

탐색 흐름은 이렇게 볼 수 있다.

순서방문 위치설명

1	1	시작 위치
2	2	1에서 2로 이동
3	4	2에서 4까지 깊게 이동
4	3	더 갈 곳이 없어 돌아온 뒤 3 방문
5	5	3에서 5 방문

DFS는 한 방향을 끝까지 가보고, 막히면 돌아와서 다른 길을 확인한다.

---

11. BFS로 탐색하면

BFS는 가까운 곳부터 차례대로 탐색한다.

1 → 2 → 3 → 4 → 5

탐색 흐름은 이렇게 볼 수 있다.

단계방문 위치설명

1단계	1	시작 위치
2단계	2, 3	1과 바로 연결된 위치
3단계	4, 5	2, 3과 연결된 다음 위치

BFS는 같은 거리의 노드들을 먼저 확인하고, 그다음 거리로 넘어간다.

---

12. 미로 최단 거리는 왜 BFS일까?

미로에서 시작점에서 도착점까지 가장 짧은 길을 찾는 문제는 BFS를 많이 사용한다.

이유는 간단하다.

BFS는 가까운 칸부터 확인하기 때문에,
도착점에 처음 도착한 순간의 거리가 최단 거리다.

예를 들어 이동 비용이 모두 1이라면,
BFS는 1칸 거리, 2칸 거리, 3칸 거리 순서로 탐색한다.

그래서 도착점을 처음 만났을 때가 가장 빠른 경로다.

반대로 DFS는 한 길을 깊게 먼저 들어가기 때문에
처음 도착한 경로가 최단 거리라는 보장이 없다.

---

13. Java에서 DFS 기본 코드

DFS는 재귀로 많이 구현한다.

static boolean[] visited;
static List<Integer>[] graph;

static void dfs(int node) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

흐름은 단순하다.

현재 노드 방문 처리
연결된 노드 확인
아직 방문하지 않았다면 다시 DFS

2차원 배열에서는 상하좌우 방향 배열을 함께 사용한다.

int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};

---

14. Java에서 BFS 기본 코드

BFS는 Queue를 사용한다.

static boolean[] visited;
static List<Integer>[] graph;

static void bfs(int start) {
    Queue<Integer> queue = new ArrayDeque<>();

    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");

        for (int next : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

BFS에서 중요한 점은 Queue에 넣을 때 방문 처리하는 것이다.

visited[next] = true;
queue.offer(next);

이렇게 해야 같은 노드가 Queue에 여러 번 들어가는 것을 막을 수 있다.

---

15. 2차원 배열에서 자주 쓰는 방향 배열

미로, 토마토, 섬 문제에서는 2차원 배열을 많이 사용한다.

상하좌우 이동은 보통 이렇게 표현한다.

int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};

방향dxdy

위	-1	0
아래	1	0
왼쪽	0	-1
오른쪽	0	1

사용할 때는 반복문으로 처리한다.

for (int dir = 0; dir < 4; dir++) {
    int nx = x + dx[dir];
    int ny = y + dy[dir];

    if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
        continue;
    }
}

---

16. 시간복잡도와 공간복잡도

DFS와 BFS는 보통 모든 노드와 간선을 한 번씩 확인한다.

그래프에서 노드 수를 V, 간선 수를 E라고 하면:

시간복잡도: O(V + E)

2차원 배열에서는 칸의 개수를 기준으로 보면 된다.

N × M 배열이라면 시간복잡도는 O(N × M)

공간복잡도는 방문 배열과 Stack/Queue 때문에 필요하다.

구조공간복잡도

visited 배열	O(V) 또는 O(N × M)
DFS 재귀 스택	최악 O(V)
BFS Queue	최악 O(V)
2차원 배열 탐색	O(N × M)

---

17. 문제 풀기 전 체크리스트

DFS/BFS 문제를 풀기 전에 아래를 먼저 확인하면 좋다.

체크 항목확인할 내용

입력 구조	그래프인가, 2차원 배열인가
정답 유형	개수인가, 거리인가, 가능 여부인가
시작점	하나인가, 여러 개인가
이동 방향	상하좌우인가, 대각선 포함인가
방문 처리	visited 배열이 필요한가
최단 거리	BFS가 필요한가
모든 경우	DFS/백트래킹이 필요한가

---

마무리

이번에 DFS/BFS를 공부하면서 가장 중요하게 느낀 점은,
두 알고리즘을 단순히 외우는 것보다 탐색의 느낌을 구분하는 것이었다.

DFS는 한 방향을 먼저 깊게 탐색한다.
하지만 한 방향만 보는 것은 아니고, 막히면 돌아와 다른 방향도 본다.

BFS는 가까운 곳부터 차례대로 탐색한다.
하지만 실제로 동시에 움직이는 것은 아니고, Queue로 하나씩 처리한다.

내가 이해한 기준은 이렇게 정리할 수 있다.

DFS = 한 길을 끝까지 가보고, 막히면 돌아와 다른 길 탐색
BFS = 가까운 곳부터 한 층씩 넓게 탐색

앞으로 문제를 볼 때는 먼저 이렇게 생각해봐야겠다.

연결된 덩어리를 찾는 문제인가?
최단 거리나 최소 횟수를 구하는 문제인가?
모든 경우를 확인해야 하는 문제인가?

이 기준만 잡아도 DFS를 쓸지 BFS를 쓸지 훨씬 쉽게 판단할 수 있을 것 같다.