[백준 1206 ] DFS와 BFS

펄어비스 코테 준비로 백준 문제이지만 프로그래머스 스타일로 코딩해봤다.

백준 1206는 DFS와 BFS 모두 구현해야하는 문제다.

https://www.acmicpc.net/problem/1260

 

//예제 입력 2
5 5 3
5 4
5 2
1 2
3 4
3 1
//예제 출력 2
3 1 2 5 4
3 1 4 2 5

//예제 입력 3
1000 1 1000
999 1000
//예제 출력 3
1000 999
1000 999

 

예제 2를 보고 양방향 연결이라는 걸 알 수 있었다.

 

예제 입력3을 보고 graph를 vector 대신 map<int, vector<int>>로 처리하고 visited은 set으로 처리해야 한다고 판단했다.

왜냐하면 vector<vector<int>>를 사용하면 정점 번호가 1부터 1000까지 모두 할당되므로, 1000개의 빈 벡터가 생성되고

visited도 vector<int> 사용시 1000개의 공간을 할당해야 하기 때문이다.

 

#include <iostream>
#include <set>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;

void DFS(map<int, vector<int>>& graph, set<int>& visited, vector<int>& answer, int n) {
    visited.insert(n);
    answer.push_back(n);
    for (int neighbor : graph[n]) {
        if (visited.count(neighbor) == 0) {
            DFS(graph, visited, answer, neighbor);
        }
    }
}

void BFS(map<int, vector<int>>& graph,vector<int>& answer, int start) {
    set<int> visited;
    visited.insert(start);
    answer.push_back(start);
    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int c_n = q.front();
        q.pop();
        for (int n : graph[c_n]) {
            if (visited.count(n) == 0) {
                visited.insert(n);
                answer.push_back(n);
                q.push(n);
            }
        }
    }
}



void solution(int N, int M, int start, map<int,vector<int>>& graph) {
    for (auto& g : graph) {
        sort(g.second.begin(), g.second.end());
    }

    vector<int> dfs_answer;
    vector<int> bfs_answer;
    set<int> visited;
    
    DFS(graph, visited, dfs_answer, start);
    BFS(graph, bfs_answer, start);
    
    for (int n : dfs_answer) {
        cout << n << " ";
    }  
    cout << '\n';
    for (int n : bfs_answer) {
        cout << n << " ";
    }
}

int main()
{
    int N, M, V;
    cin >> N >> M >> V;
    map<int, vector<int>> graph;
    for (int i = 0; i < M; ++i) {
        int n1, n2;
        cin >> n1 >> n2;
        graph[n1].push_back(n2);
        graph[n2].push_back(n1);
    }
    solution(N, M, V, graph);
}

 

조건 없이 탐색만 하면 되는 쉬운 문제였다.