백준 BaekJoon (DFS와 BFS, 1260) C++

 

완전 정석 중의 정석 문제. 풀면 DFS와 BFS의 개념에 대해서 다시 잡을 수 있다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int main() {
    int vertex = 0;
    int edge = 0;
    int first = 0;
    cin >> vertex >> edge >> first;

    vector<vector<int>> adj(vertex+1);
    vector<int> visited(vertex+1, 0);

    for(int i = 0 ; i < edge ; i++) {
        int one = 0, two =0 ;
        cin >> one >> two;

        adj[one].push_back(two);
        adj[two].push_back(one);
    }

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

    // for(int i =1 ; i <= vertex ; i++) {
    //     cout << "[ " << i << " ] ";
    //     for(int j =0 ; j < adj[i].size() ; j++) {
    //         cout << adj[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    stack<int> s;

    s.push(first);
    visited[first] = 1;
    cout << first << " ";

    while(!s.empty()) {
        int node = s.top();
        s.pop();

        for(int i = 0 ; i < adj[node].size() ; i++) {
            if(visited[adj[node][i]] == 0) {
                cout << adj[node][i] << " ";
                visited[adj[node][i]] = 1;
                s.push(node);
                s.push(adj[node][i]);
                break;
            }
        }
    }

    cout << endl;

    vector<int> visited1(vertex+1, 0);

    queue<int> q;

    q.push(first);
    visited1[first] = 1;
    cout << first << " ";

    while(!q.empty()) {
        int node = q.front();
        q.pop();

        for(int i =0 ; i < adj[node].size() ; i++) {
            if(visited1[adj[node][i]] == 0) {
                visited1[adj[node][i]] = 1;
                cout << adj[node][i] << " ";
                q.push(adj[node][i]);
            }
        }
    }
    return 0;
}