[C++] DFS & BFS

그래프 탐색은 크게 두 가지 방식이 있다.

• DFS (Depth First Search) : 깊이 우선 탐색
• BFS (Breadth First Search) : 너비 우선 탐색

---

그래프란?

정점(Vertex)과 간선(Edge)으로 이루어진 구조

• 정점: 노드
• 간선: 노드와 노드를 연결하는 선

---

🔍 DFS (깊이 우선 탐색)

✔ 개념

한 방향으로 갈 수 있을 때까지 끝까지 내려갔다가, 막히면 되돌아오는 방식

 

마치 미로 탐색처럼 동작한다.

✔ DFS 탐색 순서 예시

1 → 2 → 4 → (더 못 감) → 3 → 5

 

✔ DFS 특징

• 재귀 또는 스택으로 구현
• 한 경로를 깊게 탐색
• 백트래킹 문제에서 자주 사용

✔ DFS 사용 예

• 경로 존재 여부
• 조합, 순열
• 미로 탐색
• 트리 순회

---

DFS 구현 (재귀)

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int v) {
    visited[v] = true;
    cout << v << " ";

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

---

🔍 BFS (너비 우선 탐색)

✔ 개념

현재 위치에서 갈 수 있는 곳을 먼저 전부 탐색한 뒤, 다음 단계로 넘어가는 방식

 

물결처럼 퍼져나가는 탐색

✔ BFS 탐색 순서 예시

1 → 2 → 3 → 4 → 5

 

✔ BFS 특징

• 큐(queue) 사용
• 가까운 정점부터 탐색
• 최단 거리 문제에 최적

✔ BFS 사용 예

• 최단 거리
• 레벨 탐색
• 시작점에서 최소 이동 횟수

---

BFS 구현 (큐)

void bfs(int start) {
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur << " ";

        for (int next : graph[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

---

예제 그래프

정점은 1부터 5까지이며, 시작 정점은 1이다.
번호가 작은 정점부터 방문한다고 가정한다.

    1
   / \
  2   3
   \   \
    4   5

간선:

• 1 - 2
• 1 - 3
• 2 - 4
• 3 - 5

---

DFS (Depth First Search)

개념

DFS는 한 방향으로 갈 수 있을 때까지 끝까지 이동한 뒤, 더 이상 갈 수 없으면 되돌아오는 방식이다.
재귀 호출이나 스택을 사용한다.

DFS 탐색 과정

1단계

• 시작 정점 1 방문

방문: 1

 

2단계

• 1에서 갈 수 있는 가장 작은 정점 → 2

방문: 2

 

3단계

• 2에서 갈 수 있는 정점 → 4

방문: 4

 

4단계

• 4는 더 이상 갈 곳이 없음 → 되돌아감

5단계

• 2도 더 이상 갈 곳이 없음 → 되돌아감

6단계

• 1에서 아직 방문하지 않은 정점 → 3

방문: 3

 

7단계

• 3에서 갈 수 있는 정점 → 5

방문: 5

---

DFS 최종 방문 순서

1 → 2 → 4 → 3 → 5

---

BFS (Breadth First Search)

개념

BFS는 현재 위치에서 갈 수 있는 모든 정점을 먼저 방문한 뒤, 다음 단계로 이동한다.
큐(queue)를 사용한다.

BFS 탐색 과정

1단계

• 시작 정점 1 방문
• 큐에 1 삽입

큐: [1]

 

2단계

• 1에서 갈 수 있는 정점 모두 방문 (2, 3)

큐: [2, 3]

 

3단계

• 2를 꺼내고, 갈 수 있는 정점 4 방문

큐: [3, 4]

 

4단계

• 3을 꺼내고, 갈 수 있는 정점 5 방문

큐: [4, 5]

 

5단계

• 4, 5는 더 이상 갈 곳이 없음
• 큐가 비면 종료

---

BFS 최종 방문 순서

1 → 2 → 3 → 4 → 5

---

DFS와 BFS 비교

구분DFSBFS

탐색 방식	깊이 우선	너비 우선
사용 자료구조	스택 / 재귀	큐
최단 거리	보장 X	보장 O
탐색 특징	한 경로 집중	레벨 단위 탐색

---

언제 어떤 탐색을 사용할까?

DFS 사용 상황

• 모든 경우를 탐색해야 할 때
• 경로 존재 여부
• 조합, 순열, 백트래킹 문제

BFS 사용 상황

• 최단 거리 문제
• 최소 이동 횟수
• 단계별 탐색이 필요한 경우

---

백준 1260 (DFS와 BFS) 전체 코드 예제

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int v) {
    visited[v] = true;
    cout << v << " ";

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

void bfs(int start) {
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur << " ";

        for (int next : graph[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, V;
    cin >> N >> M >> V;

    graph.resize(N + 1);
    visited.resize(N + 1, false);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // 작은 번호부터 방문하기 위해 정렬
    for (int i = 1; i <= N; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    // DFS
    dfs(V);
    cout << '\n';

    // 방문 배열 초기화
    fill(visited.begin(), visited.end(), false);

    // BFS
    bfs(V);
    cout << '\n';

    return 0;
}