[백준] 1260 DFS와 BFS

DFS와 BFS 기본문제다

제목 그대로 DFS와 BFS를 실행시키면 된다

이 때 정점 번호가 작은 것을 먼저 방문하므로 정렬을 해줘야한다!

c_cnt를 이용해 방문지점을 체크하는 check배열을 구별할 수 있다

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m,s,check[1010],c_cnt=1;
vector<vector<int>> Graph;
 
void dfs(int x) {
    check[x] = c_cnt;
    printf("%d ", x);
 
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (check[next] != c_cnt) dfs(next);
    }
}
 
void bfs(int x) {
    queue<int> q;
    q.push(x);
    check[x] = c_cnt;
    while (!q.empty()) {
        int here = q.front();
        q.pop();
        printf("%d ", here);
        for (int i = 0; i < Graph[here].size(); i++) {
            int next = Graph[here][i];
            if (check[next] != c_cnt) {
                check[next] = c_cnt;
                q.push(next);
            }
        }
    }
}
int main() {
    scanf(" %d %d %d", &n, &m, &s);
    Graph.resize(n+1);
    for (int i = 0; i < m; i++) {
        int u, v; scanf(" %d %d", &u, &v);
        Graph[u].push_back(v);
        Graph[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) sort(Graph[i].begin(), Graph[i].end());
    dfs(s); puts("");
    c_cnt++;
    bfs(s);
}