깊이 우선 탐색 DFS, 넓이 우선 탐색 BFS

 

 

Depth First Search (DFS) : 깊이 우선 탐색

Breadth First Search (BFS) : 넓이 우선 탐색

 

깊이 우선 탐색은 자식노드를 타고 쭉쭉 내려갔다가, 다시 올라와서 그다음 줄기를 탐색하는 것을 말하고

너비 우선 탐색은 자식노드를 모두 방문하고, 그 자식의 자식노드를 방문하는 식의 탐색을 말한다

 

DFS는 Stack을 이용해서 구현하고, BFS는 Queue로 구현한다

Stack은 Last In First Out, Queue는 First In First Out 인데 이 점을 이용하여 구현하는 것이다

DFS는 재귀호출을 통하여 더 쉽고 편리하게 구현할 수 있다

 

---

백준 알고리즘 1260 DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다

 

벡터에 이런식으로 넣어서 표현할 수 있다

 

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

 

그리고 정점 번호가 작은 것을 먼저 방문한다고 했기 때문에 노드별로 정렬을 해줘야 한다

 

    for (int i = 0; i < n; i++) {
        sort(v[i].begin(), v[i].end());
    }

 

이제 dfs와 bfs를 호출하면 되는데, v(코드의 start)를 인자로 전달하여 시작점이 될 수 있게 한다

 

 

먼저 dfs 함수

 

void dfs(int start) {
    visited[start] = true;
    cout << start << ' ';
    for (int i = 0; i < v[start].size(); i++) {
        int node = v[start][i];
        if (!visited[node]) dfs(node);
    }
}

 

방문했다(visited) 체크하고, 출력부터 해준다!! 출력 나중에 하면 역순 됨

그리고 방문하지 않은 자식노드를 인자값으로 함수를 계속 호출한다

 

 

bfs 함수

 

void bfs(int start) {
    visited2[start] = true;
    q.push(start);
 
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << ' ';
 
        for (int i = 0; i < v[node].size(); i++) {
            int next = v[node][i];
            if (!visited2[next]) {
                visited2[next] = true;
                q.push(next);
            }
        }
    }
}

 

FIFO를 이용해야 하므로 큐 변수 q를 만들었다

먼저 시작점에 visited 체크하고, q에 push해준다

그 뒤로는 pop하고.. 자식노드들 push하고.. 의 반복

 

bfs는 재귀가 아닌 반복문을 사용하는데

탐색이 끝나면 큐가 비므로 while 조건은 !q.empty()가 된다

 

이제 층별로 탐색하면 됨

next는 node의 자식노드인데, 방문한 적 없다면 visited 체크하고, q에 넣어주면 된다

 

 

 

전체코드

 

 

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
 
vector<int> v[1001];
bool visited[1001];
bool visited2[1001];
queue<int> q;
 
void dfs(int start) {
    visited[start] = true;
    cout << start << ' ';
    for (int i = 0; i < v[start].size(); i++) {
        int node = v[start][i];
        if (!visited[node]) dfs(node);
    }
}
 
void bfs(int start) {
    visited2[start] = true;
    q.push(start);
 
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << ' ';
 
        for (int i = 0; i < v[node].size(); i++) {
            int next = v[node][i];
            if (!visited2[next]) {
                visited2[next] = true;
                q.push(next);
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, m, start;
    int a, b;
 
    cin >> n >> m >> start;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    for (int i = 0; i < n; i++) {
        sort(v[i].begin(), v[i].end());
    }
 
    dfs(start);
    cout << "\n";
 
    bfs(start);
    cout << "\n";
}

 

막상 구현하면 크게 어렵지 않다

이제 이걸로 응용을 하니 문제지만..^^ (빵집의 추억ㅎ)