BFS & DFS (C++ )

BFS와 DFS는 그래프·트리·격자(Grid) 문제의 출발점이 되는 핵심 탐색 알고리즘입니다.

 

1. BFS (Breadth-First Search, 너비 우선 탐색)

“최단 거리”가 보이면 → BFS부터 의심하자

BFS는 가까운 노드부터 차례대로 탐색합니다.
그래서 처음 도달한 순간의 거리 = 최단 거리가 됩니다
(단, 모든 간선 가중치가 동일할 때).

🔹 핵심 특징

• 탐색 방식: 레벨(Depth) 순 탐색
• 대표 문제 유형
  • 최단 거리 / 최소 이동 횟수
  • 미로 탈출
  • 시작점에서 퍼져나가는 전염/확산 문제

🔹 핵심 도구

• std::queue

🔹 C++에서 반드시 지켜야 할 포인트

• push와 동시에 방문 처리
  • 큐에 넣을 때 visited = true
  • 꺼낼 때 방문 처리 ❌ → 중복 push → 메모리 초과 위험

q.push({x, y});
visited[x][y] = true;  // 반드시 여기서

BFS에서 방문 처리는 큐 관리 전략이지, 단순한 체크가 아닙니다.

---

2. DFS (Depth-First Search, 깊이 우선 탐색)

“모든 경우를 다 봐야 한다” → DFS

DFS는 한 방향으로 끝까지 파고드는 탐색 방식입니다.
모든 경우의 수를 확인하거나, 구조 자체를 파악하는 문제에 강합니다.

🔹 핵심 특징

• 탐색 방식: 한 방향으로 깊게 → 더 이상 못 가면 되돌아옴
• 대표 문제 유형
  • 모든 경로 탐색
  • 연결 요소(Connected Components) 개수
  • 백트래킹 문제의 기본 뼈대

🔹 핵심 도구

• 재귀 함수
• 또는 std::stack

🔹 C++에서 반드시 주의할 점

1. 재귀 깊이 제한
   • 깊이가 10^5 이상이면 스택 오버플로우 위험
   • 이런 경우 반복문 + stack으로 전환 고려
2. 종료 조건 명확히
   • 방문 처리 시점과 종료 조건이 애매하면 무한 재귀로 직행

void dfs(int x, int y) {
    visited[x][y] = true;

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (/* 범위 OK && 방문 안 함 */) {
            dfs(nx, ny);
        }
    }
}

 

DFS (Stack 활용) 기본 수도코드

stack 생성
시작 노드를 stack에 push
시작 노드를 방문 처리

while stack이 비어있지 않다면:
    현재 노드 ← stack의 top
    stack에서 pop

    for 각 인접한 다음 노드:
        if 아직 방문하지 않았다면:
            다음 노드를 방문 처리
            stack에 push

 

 

Stack DFS에서 자주 하는 실수 ⚠️

1. pop 후 방문 처리
   • ❌ 중복 push 발생
   • ✅ push할 때 방문 처리
2. DFS처럼 쓰고 싶다고 LIFO를 잊는 경우
   • stack → LIFO
   • queue → FIFO (BFS)
3. 순서가 문제에 영향을 주는 경우
   • stack DFS는 탐색 순서가 재귀 DFS와 다를 수 있음
   • 결과가 순서 의존적인 문제면 주의

---

재귀 DFS vs Stack DFS 한 줄 요약

구분	재귀 DFS	stack DFS
구현 난이도	쉬움	약간 번거로움
깊이 제한	❌ 있음	✅ 없음
코테 안정성	보통	높음

👉 “DFS인데 깊이 커 보인다” → stack 버전 자동 선택 가능 👍

 

---

3. 코딩 테스트 실전 꿀팁 (C++ 중심)

① 2차원 배열 탐색은 방향 배열이 국룰

격자 문제에서 방향 배열은 가독성 + 실수 방지를 동시에 잡아줍니다.

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

for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    // 범위 체크 + visited 확인
}

👉 대각선까지 포함하면 8방향,
👉 말 이동 / 커스텀 이동은 배열만 바꾸면 끝.

---

② 방문 배열 초기화는 습관처럼

여러 테스트 케이스가 있는 문제에서
방문 배열 초기화를 깜빡하면 이유 모를 오답이 나옵니다.

#include <cstring>
memset(visited, 0, sizeof(visited));

• 0 / 1 → 방문 여부
• -1 → 거리 배열 초기값으로도 자주 사용

---

③ Fast I/O는 기본 세팅

코테에서는 입출력 속도도 실력입니다.

ios::sync_with_stdio(false);
cin.tie(nullptr);

• 한 번만 써두면 끝
• 안 써서 손해 볼 이유 ❌

---

4. BFS vs DFS, 이렇게 구분하자

상황추천

최단 거리, 최소 이동	BFS
모든 경우 탐색	DFS
연결 요소 개수	DFS
레벨 단위 확산	BFS
백트래킹 기반 문제	DFS