[백준] 1260 - DFS와 BFS, C++

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

1260번: DFS와 BFS

 본 문제는 백준 1260 문제로 DFS와 BFS를 코딩할 줄 아는지 물어보는 문제다. DFS와 BFS를 구현할 줄 알면 쉬운 문제다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
vector<int> v[1001];
bool chk[1001];
 
void dfs(int now) {
    chk[now] = true;
    printf("%d ", now);
    for (int i = 0; i < v[now].size(); i++) {
        int next = v[now][i];
        if (!chk[next]) dfs(next); 
    }
}
 
int main() {
    int n, m, start, a, b;
    scanf("%d %d %d", &n, &m, &start);
    // 간선 입력
    for (int i = 0; i < m; i++) {         
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    // 조건) 정점 번호가 작은것을 먼저 방문한다.
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end());
    }
    dfs(start);
    printf("\n");
    // chk 초기화
    for (int i = 1; i <= n; i++) {
        chk[i] = false;
    }
    queue<int> q;
    q.push(start);
    chk[start] = true;
    while (!q.empty()) {
        int now = q.front();
        printf("%d", now);
        q.pop();
        for (int i = 0; i < v[now].size(); i++) {
            int next = v[now][i];
            if (!chk[next]) {
                chk[next] = true;
                q.push(next);
            }
        }
        if (!q.empty()) printf(" ");
    }
    return 0;
}