DFS와 BFS 차이 정리 | 코딩테스트에서 문제에 맞게 고르는 기준

DFS와 BFS는 정의만 외우면 계속 헷갈린다.

실제로 코테에서 중요한 건

“DFS는 깊이 우선, BFS는 너비 우선” 같은 문장 자체가 아니라,

문제를 봤을 때 어느 쪽이 더 자연스러운지 판단하는 기준이다.

정리하면 이렇다.

• 최단거리 / 레벨 / 한 칸씩 퍼지는 구조면 보통 BFS가 맞고
• 연결된 덩어리 처리 / 끝까지 파고들기 / 완전탐색이면 DFS가 더 자연스러운 경우가 많다

즉, DFS/BFS는 알고리즘 이름을 외우는 문제가 아니라

문제 구조를 보고 고르는 문제에 가깝다.

이 글에서는 그 기준만 정리해보려고 한다.

---

🔗 주제

DFS와 BFS 차이 정리

---

개념 요약

둘 다 탐색이다.

즉, 그래프나 격자에서 어떻게 방문할지를 정하는 방식이다.

차이는 방문 순서다.

DFS

• 한 방향으로 끝까지 들어간다
• 막히면 돌아온다
• 스택 흐름이랑 잘 맞는다

BFS

• 가까운 곳부터 넓게 퍼진다
• 먼저 들어간 걸 먼저 꺼낸다
• 큐 흐름이랑 잘 맞는다

이게 정의인데,

코테에서는 여기서 한 단계 더 나가서 봐야 한다.

---

✅ 핵심 아이디어

실전에서는 보통 이렇게 구분하면 된다.

BFS가 더 자연스러운 경우

• 최단거리 문제
• 시작점에서 몇 단계 떨어졌는지 중요할 때
• 한 칸씩 퍼지는 구조
• 같은 가중치로 이동할 때

DFS가 더 자연스러운 경우

• 연결된 영역 개수 세기
• 한 덩어리 전체를 방문 처리할 때
• 경로를 끝까지 따라가야 할 때
• 재귀 구조가 더 직관적일 때

즉, 핵심은

방문 순서보다 문제 목표다.

---

대표 코드

DFS 기본형

def dfs(graph, start):
    need_visit = [start]
    visited = []

    while need_visit:
        node = need_visit.pop()

        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited

이 구조는 리스트를 스택처럼 쓰는 형태다.

• 뒤에 넣고
• 뒤에서 뺀다

즉, 가장 최근에 넣은 노드를 먼저 처리한다.

---

BFS 기본형

from collections import deque

def bfs(graph, start):
    q = deque([start])
    visited = []

    while q:
        node = q.popleft()

        if node not in visited:
            visited.append(node)
            q.extend(graph[node])

    return visited

이 구조는 deque를 큐처럼 쓰는 형태다.

• 뒤에 넣고
• 앞에서 뺀다

즉, 먼저 들어간 노드를 먼저 처리한다.

---

생각해야 하는 부분

이 글에서 중요한 건

DFS/BFS를 정의로만 나누지 말고,

문제 유형이랑 연결해서 보는 것이다.

---

1. 최단거리면 BFS부터 보는 게 맞다

이건 거의 기준처럼 가져가도 된다.

예를 들면 백준 18352 특정 거리의 도시 찾기 같은 문제는

출발점에서 정확히 몇 칸 떨어졌는지가 중요했다.

이럴 때는 BFS가 자연스럽다.

왜냐면 BFS는 이렇게 진행되기 때문이다.

• 시작점
• 1칸 떨어진 노드들
• 2칸 떨어진 노드들
• 3칸 떨어진 노드들

즉, 레벨 순서대로 탐색한다.

그래서 최단거리나 거리 배열이 필요한 문제는

대체로 BFS부터 보면 된다.

---

2. 연결된 덩어리 개수 세기는 DFS가 잘 맞는다

예를 들면 얼음 얼려 먹기 같은 문제는

최단거리가 중요한 게 아니라

“연결된 0 덩어리가 몇 개인가”를 세는 게 핵심이었다.

이럴 때는 BFS도 가능하긴 하지만,

DFS 재귀가 더 직관적이다.

왜냐면 DFS는

지금 시작한 지점에서 연결된 곳을 전부 끝까지 밀어버리기에 좋기 때문이다.

즉, 이런 문제는 보통 이렇게 생각하면 된다.

• 새 시작점 찾기
• DFS로 그 덩어리 전체 방문 처리
• 개수 1 증가

이 패턴이면 DFS가 잘 맞는다.

---

3. 격자 문제는 BFS/DFS보다 먼저 “좌표 문제”로 봐야 한다

이건 많이 놓친다.

예를 들어 백준 2178 미로 탐색은 BFS 문제이긴 한데,

사실 먼저 봐야 하는 건

이게 일반 그래프가 아니라 좌표형 문제라는 점이다.

즉,

• 노드 = 번호가 아니라 (x, y)
• 인접 노드 = 상하좌우 직접 계산
• 범위 체크 먼저

이 구조가 먼저 잡혀야

그다음 BFS든 DFS든 들어간다.

즉, DFS/BFS를 고르기 전에

문제를 어떤 노드 구조로 볼 것인지를 먼저 정해야 한다.

---

4. DFS/BFS보다 자료구조가 같이 따라온다

이것도 중요하다.

DFS

보통 스택 흐름이라서

리스트 + pop()으로 많이 구현한다.

stack = []
stack.append(start)
node = stack.pop()

BFS

보통 큐 흐름이라서

deque + popleft()로 구현한다.

from collections import deque

q = deque([start])
node = q.popleft()

즉, DFS/BFS는 알고리즘 이름만 떠올릴 게 아니라

어떤 자료구조를 같이 쓸지까지 묶어서 생각하는 게 맞다.

---

예외처리 / 주의할 점

⚠️ 1. BFS가 항상 더 좋은 건 아니다

최단거리 문제면 BFS가 강한 건 맞는데,

그렇다고 BFS가 항상 정답은 아니다.

예를 들어 연결 요소 개수 세기 같은 문제는

DFS가 더 직관적인 경우가 많다.

즉, “탐색 = BFS” 식으로 단순하게 가면 안 된다.

---

⚠️ 2. DFS/BFS보다 먼저 노드 구조를 봐야 한다

이건 특히 격자 문제에서 많이 헷갈린다.

• 일반 그래프 → 인접 리스트
• 격자 → (x, y) 좌표 + dx, dy
• 출발점 하나 → 탐색 1번
• 출발점 여러 개 → 전체 순회 안에 탐색 포장

문제를 어떤 구조로 볼지 먼저 정하지 않으면

DFS/BFS 선택도 애매해진다.

---

⚠️ 3. 방문 처리 방식도 문제마다 다르다

방문 처리도 고정된 정답이 없다.

예를 들어

• 18352 → distance 배열
• 미로 탐색 → graph 자체를 거리값으로 덮어쓰기
• 얼음 문제 → 0을 1로 바꾸기

이렇게 문제마다 다 다르다.

즉, DFS/BFS를 고른 뒤에는

방문을 뭘로 기록할지까지 같이 설계해야 한다.

---

내 시행착오

이건 나도 초반에 꽤 헷갈렸던 부분이다.

---

1. DFS/BFS를 그냥 정의로만 외우려고 했다

처음엔 나도

• DFS = 깊이 우선
• BFS = 너비 우선

이 정도만 외우려고 했다.

근데 문제 풀 때는 그걸로 잘 안 풀린다.

실전에서는

“이 문제는 최단거리냐?”,

“이 문제는 덩어리 세기냐?”

이렇게 연결해서 봐야 훨씬 잘 잡힌다.

---

2. BFS/DFS를 고르기 전에 노드 구조를 안 봤다

예를 들어 미로 탐색 같은 문제는

BFS냐 DFS냐보다 먼저

이게 좌표 문제라는 걸 먼저 잡아야 했다.

그걸 놓치면 알고리즘 선택 이전에 구현부터 꼬인다.

---

3. DFS/BFS를 고르면 끝이라고 생각했다

실제로는 거기서 끝이 아니다.

그다음엔 항상 같이 생각해야 한다.

• 큐냐 스택이냐
• visited를 따로 둘 거냐
• graph를 덮어쓸 거냐
• distance 배열을 둘 거냐

즉, DFS/BFS는 시작이지 끝이 아니다.

---

4. “문제에 맞는 탐색”이라는 개념이 늦게 잡혔다

처음엔 탐색 문제를 보면

그냥 배운 DFS/BFS를 억지로 끼워 맞추려고 했다.

근데 지금 보면 순서가 반대였다.

• 문제를 먼저 보고
• 구조를 파악하고
• 거기에 맞는 탐색을 고른다

이 흐름이 맞았다.

---

한 줄 정리

DFS와 BFS는 정의로 외우는 게 아니라,

문제가 최단거리인지 / 연결 요소인지 / 좌표형인지에 따라 고르는 탐색 방식으로 보는 게 맞다.