(C++) 백준 1260번 - DFS와 BFS

문제 링크 : https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

풀이

그래프에서의 DFS와 BFS를 구현하는 문제이다.

DFS는 Stack을, BFS는 Queue를 사용해서 풀력 형식에 맞게 그래프의 정점을 하나씩 순회하도록 구현하면 된다.

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

using namespace std;

vector<int> gp[1002];
int visited[1002];
queue<int> q;
stack<int> s;
int n, m, v, x, y;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> v;
    while(m--){
        cin >> x >> y;
        gp[x].push_back(y);
        gp[y].push_back(x);
    }

    for(int i = 1; i <= n; i++) {
        sort(gp[i].begin(), gp[i].end());
        reverse(gp[i].begin(), gp[i].end());
    }

    s.push(v);
    while(!s.empty()){
        int pre = s.top();
        s.pop();
        if(visited[pre]) continue;
        visited[pre] = 1;
        cout << pre << " ";
        for(auto k : gp[pre]){
            if(visited[k]) continue;
            s.push(k);
        }
    }
    cout << "\n";

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

    fill_n(visited, 1002, 0);
    q.push(v);
    while(!q.empty()){
        int pre = q.front();
        q.pop();
        if(visited[pre]) continue;
        visited[pre] = 1;
        cout << pre << " ";
        for(auto k : gp[pre]){
            if(visited[k]) continue;
            q.push(k);
        }
    }
}