1260: DFS와 BFS

• toc {:toc}

문제 확인하기

풀이

DFS/BFS 에 대한 이해를 묻는 문제이다. 그래프를 형성해주고 DFS/BFS를 구현한다. 이 때, 방문 가능한 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점에 주의한다. BFS와 DFS의 작동원리를 생각하면서 풀이하자. 아래 코드는 DFS를 재귀적으로 풀이한 방식이다.

#include <bits/stdc++.h>
using namespace std;
 
vector<int> graph[1005];
vector<pair<int, int>> vec;
queue<int> q;
stack<int> st;
int visit[1005];
 
void dfs(int v){
    visit[v] = 1;
    cout << v << ' ';
    for(auto link : graph[v]){
        if(visit[link] == 0)
            dfs(link);
    }
}
void bfs(){
    while(!q.empty()){
        int v = q.front(); q.pop();
        cout << v << ' ';
        for(auto link : graph[v]){
            if(visit[link] == 0){
                q.push(link);
                visit[link] = 1;
            }
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int N, M, V, val1, val2;
 
    cin >> N >> M >> V;
 
    for(int i=0; i < M; i++){
        cin >> val1 >> val2;
        if(val1 < val2)
            vec.push_back({val1, val2});
        else
            vec.push_back({val2, val1});
    }
    sort(vec.begin(), vec.end());
 
    for(int i=0; i < vec.size(); i++){
        val1 = vec[i].first;
        val2 = vec[i].second;
        // 무방향 그래프
        graph[val1].push_back(val2);
        graph[val2].push_back(val1);
    }
 
    dfs(V);
    cout << '\n';
    fill(visit, visit+N+1, 0);
 
    q.push(V);
    visit[V] = 1;
    bfs();
 
    return 0;
}

다음의 방식은 DFS를 스택을 사용해서 구현한 방식이다. 일반적인 바둑판 배열에서는 4 방향으로 이동하면서 조건에 따라 한 번씩 스택에 push 해주면 되지만, 무방향 그래프에서는 break와 push를 두 번 해줌으로써 DFS를 구현했다.

왜 push를 두 번 해줘야 할까?

4 5 1 1 2 1 3 1 4 2 4 3 4

다음의 입력을 생각해보자. 1을 시작으로 들어갔을 때 방문 가능한 정점이 여러 개이기 때문에 번호가 작은 것을 더 먼저 방문해야 한다.

• graph(1)에 들어갔을 때 2, 3, 4 에 방문 가능하므로 2를 push하고 break한다.
• 이 후 2가 스택에서 pop()되어 출력되고 2와 연결된 노드 4로 이동하게 된다.
• 4가 스택에서 pop()되어 3으로 이동한다. 다음의 방식으로 진행하면 깊이 우선 방식으로 진행 가능하다.

3 2 1 1 3 2 1 하지만, 다음의 입력을 생각해보자.

• 1에 들어갔을 때 2, 3에 방문 가능하고, 2를 push 하고 break한다.
• 2에 들어갔을 때 1에 방문 가능하지만 이미 방문 했기에 넘어간다.
• DFS가 끝난다. (1, 2 만 출력)

위의 경우처럼 한 번만 push할 경우 다수 정점에 방문 가능한 정점에서 놓치는 정점이 존재하게 된다. 따라서, break 하는 대신 다시 한 번 다수 정점을 가진 정점을 push 하면서 놓치는 정점이 없도록 만든다.

#include <bits/stdc++.h>
using namespace std;
 
vector<int> graph[1005];
vector<pair<int, int>> vec;
queue<int> q;
stack<int> st;
int visit[1005];
 
void dfs(){
    int v = st.top();
    cout << v << ' ';
    while(!st.empty()){
        v = st.top(); st.pop();
        for(auto link : graph[v]){
            if(visit[link] == 0){
                visit[link] = 1;
                cout << link << ' ';
                st.push(v);
                st.push(link);
                break;
            }
        }
    }
}
 
void bfs(){
    while(!q.empty()){
        int v = q.front(); q.pop();
        cout << v << ' ';
        for(auto link : graph[v]){
            if(visit[link] == 0){
                q.push(link);
                visit[link] = 1;
            }
        }
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int N, M, V, val1, val2;
 
    cin >> N >> M >> V;
 
    for(int i=0; i < M; i++){
        cin >> val1 >> val2;
        if(val1 < val2)
            vec.push_back({val1, val2});
        else
            vec.push_back({val2, val1});
    }
    sort(vec.begin(), vec.end());
 
    for(int i=0; i < vec.size(); i++){
        val1 = vec[i].first;
        val2 = vec[i].second;
        // 무방향 그래프
        graph[val1].push_back(val2);
        graph[val2].push_back(val1);
    }
 
    st.push(V);
    visit[V] = 1;
    dfs();
    cout << '\n';
    fill(visit, visit+N+1, 0);
 
    q.push(V);
    visit[V] = 1;
    bfs();
 
    return 0;
}