baekjoon - (DFS와 BFS)

난이도 : Silver 2

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

예제 입력 1 복사

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

예제 출력 1 복사

1 2 4 3
1 2 3 4

 

풀이)

해당 문제는 깊이우선탐색(DFS)와 넓이우선탐색(BFS)를 이용하는 기초 문제이다. 

먼저 1->2 , 1->3, 1->4 이렇게 노드와 간선이 연결되어 있는 형태를 컨테이너에 저장해야한다.

필자는 Map을 활용해서 저장을 할 예정이며, 예를 들어 1번 노드에 여러 간선이 있을 수 있으니 int와 vector<int>를 이용하려고 한다.

 

먼저 DFS는 깊이 우선 탐색인 만큼 현재 위치에서 다음위치 다음 위치에 연결되어있는 위치 이렇게 계속 깊게 파고 들어야한다. 필자는 재귀를 통해서 다음 노드에 방문을 할 것이며 재귀를 통해 현재 위치해 있는 곳에서 계속 깊게 팔 수 있을 것이다. 그러면 함수가 시작되고, 나는 방문을 했다라는 걸 알아야하니까 방문 했다라는 bool 변수를 사용하면서 방문을 하였고, 다음 연결되어 있는 노드들에서 다시 첫번째부터 방문이 안된 지역을 다시 방문하는 형태로 구성해보았다.

 

그리고 BFS는 Queue를 이용하여 풀게 되었다.

함수가 시작되면 Queue에 현재 위치를 넣고, Queue가 비어있을때 까지 (방문할 곳이 없을 때) 반복문을 돌게 된다.

그리고 현재 위치를 Queue에서 빼서 가져온 다음 반복문을 통해서 현재 노드에 연결되어 있는 곳을 Queue에 전부 넣어서 해당 작업을 반복하면 결국 연결되어 있는 곳을 전부 방문하게 되는 형태이다.

 

*코드에 주석으로 조금 더 알아보기 쉽게 해보겠다.

 

코드)

#include <bits/stdc++.h>
using namespace std;

 

//방문했는지 여부
bool visitedD[100001];
bool visitedB[100001];

map<int, vector<int>> m; 

 

void DFS(map<int, vector<int>> &m, int current){
    //현재 위치 방문

    visitedD[current] = true;
    
    cout << current << " ";

    //현재 위치에 연결되어 있는 부분들을 재귀를 통해 방문
    for(int next : m[current]){
        if(!visitedD[next]){
            DFS(m, next);
        }
    }
}

queue<int> q;
void BFS(map<int, vector<int>> &m, int source){

    //현재 위치를 방문과 함께 Queue에 삽입
    q.push(source);
    visitedB[source] = true;
    

    //Queue가 빌때까지 반복
    while(!q.empty()){
        int current = q.front();
        q.pop();    
        cout << current << " "; 

        //현재 노드에 저장되어 있는 수 만큼 방문예정을 한다. (다음 방문지역을 넣는다.) 
        for(int next : m[current]){
            if(!visitedB[next]){
                q.push(next);
                visitedB[next] = true;
            }
        }
    }
}
int main() {
    int N, M, V;
    cin >> N >> M >> V;
    
    for(int i=0; i<M; i++){
        int first, second;
        cin >> first >> second;
    
        m[first].push_back(second);
        m[second].push_back(first);
    }
    

 // 인접 리스트가 정렬되지 않으면 탐색 순서가 달라질 수 있다.
    for(auto &iter : m){
        sort(iter.second.begin(), iter.second.end());
    }
    
    DFS(m, V);
    cout << endl;
    BFS(m, V);
    return 0;
}