DFS/BFS

DFS (Depth-First Search)

1. DFS란?

DFS는 깊이 우선 탐색이라 하며, 한 정점에서 시작해 갈 수 있는 한 깊이 들어갔다가, 더 이상 갈 수 없으면 이전 지점으로 되돌아오는(backtracking) 방식의 그래프 탐색 알고리즘이다.
스택(Stack) 자료구조를 사용하거나, 재귀 호출을 통해 시스템 호출 스택을 활용한다.

---

2. DFS의 원리

1. 시작 정점을 방문하고 방문 표시를 한다.
2. 현재 정점에서 갈 수 있는 이웃 정점 중 아직 방문하지 않은 정점을 하나 선택해 이동한다.
3. 이동한 정점에서 1~2 과정을 반복한다.
4. 더 이상 방문할 이웃이 없으면 이전 정점으로 되돌아가 다른 경로를 탐색한다.
5. 모든 정점을 방문할 때까지 반복한다.

---

3. 반복형 DFS 코드

vector<int> dfs_iter(int start, const vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    vector<int> order;
    stack<int> st;

    st.push(start);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        order.push_back(u);

        // 역순으로 push → 방문 순서 제어
        for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {
            if (!visited[*it]) st.push(*it);
        }
    }
    return order;
}

---

4. 데이터 흐름 예시 (시작 정점 1)

그래프 예시 (무방향, 오름차순 정렬됨):

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

단계	Pop한 정점	스택 상태(Top 오른쪽)	visited 벡터 상태 (1=방문)	동작
초기	-	[1]	[0,0,0,0,0,0]	시작 정점 push
1	1	[3,2]	[0,1,0,0,0,0]	1 방문, 이웃 3,2 역순 push
2	2	[3,5,4]	[0,1,1,0,0,0]	2 방문, 이웃 5,4,1 역순 push
3	4	[3,5]	[0,1,1,0,1,0]	4 방문, 이웃 2 이미 방문
4	5	[3,3]	[0,1,1,0,1,1]	5 방문, 이웃 3 미방문 push
5	3	[3]	[0,1,1,1,1,1]	3 방문, 이웃 5,1 방문됨
6	3	[]	[0,1,1,1,1,1]	이미 방문 skip

최종 방문 순서: 1 → 2 → 4 → 5 → 3

---

5. 재귀형 DFS 코드

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

using namespace std;

void DFS(vector<vector<int>>& arr, vector<bool>& visited, int num) {
    if (visited[num]) return;
    visited[num] = true;
    cout << num << " ";

    for (int i : arr[num]) {
        DFS(arr, visited, i);
    }
}

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

    int node, edge, start;
    cin >> node >> edge >> start;

    vector<vector<int>> arr(node + 1);
    vector<bool> visited(node +1,false);

    for (int i = 0; i < edge; i++) {
        int s, e;
        cin >> s >> e;
        arr[s].push_back(e);
        arr[e].push_back(s);
    }

    for (int i = 1; i <= node; i++) {
        sort(arr[i].begin(), arr[i].end());
    }

    DFS(arr, visited, start);

    return 0;
}

---

BFS (Breadth-First Search)

1. BFS의 정의

BFS는 너비 우선 탐색이라 하며, 시작 정점에서 가까운 정점부터 차례대로 방문하는 알고리즘이다.
큐(Queue) 자료구조를 사용하며, 무가중치 그래프에서 최단 거리 탐색에 자주 사용된다.

---

2. BFS의 원리

1. 시작 정점을 큐에 넣고 방문 표시를 한다.
2. 큐에서 정점을 하나 꺼낸다.
3. 해당 정점의 이웃 중 아직 방문하지 않은 정점을 모두 큐에 넣고 방문 표시한다.
4. 큐가 빌 때까지 2~3 과정을 반복한다.

---

3. BFS 코드

void bfs_iter(const vector<vector<int>>& g, int s) {
    vector<bool> visited(g.size(), false);
    queue<int> q;
    q.push(s);
    visited[s] = true;

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

        // 큐는 FIFO라 정방향으로 넣으면 오름차순 방문이 자연스러움
        for (int nxt : g[cur]) {
            if (!visited[nxt]) {
                visited[nxt] = true;
                q.push(nxt);
            }
        }
    }
}

---

4. 데이터 흐름 예시 (시작 정점 1)

그래프 예시 (DFS와 동일):

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

방문 과정 표

단계	Dequeue 한 정점	큐 상태(Front 왼쪽)	visited 벡터 상태 (1=방문)	동작
초기	-	[1]	[0,1,0,0,0,0]	시작 정점 enqueue
1	1	[2,3]	[0,1,1,1,0,0]	1 방문, 이웃 2,3 enqueue
2	2	[3,4,5]	[0,1,1,1,1,1]	2 방문, 이웃 4,5 enqueue
3	3	[4,5]	[0,1,1,1,1,1]	3 방문, 이웃 모두 방문됨
4	4	[5]	[0,1,1,1,1,1]	4 방문, 이웃 방문됨
5	5	[]	[0,1,1,1,1,1]	5 방문, 이웃 방문됨

최종 방문 순서: 1 → 2 → 3 → 4 → 5

 

그리고 이걸 알아보면서 auto,rbegin,rend라는 친구들이 있는데 좀 생소해서 다음글에서 알아보려 한다.