BOJ 1260번 DFS와 BFS

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1260/1260/%EC%86%8C%EC%8A%A4.cpp

 

dfs bfs 의 기본지식을 묻는 문제이다.

작은정점부터 방문하라 했으니 정렬을 해줘야한다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
int N, M, start;
int s, e;
vector<int> v[1001];
bool visit[1001];
 
void dfs(int start) {
    if (visit[start]) return;
    visit[start] = 1;
    cout << start << " ";
 
    for (int i = 0; i < v[start].size(); i++) {
        dfs(v[start][i]);
    }
}
 
void bfs(int start) {
    queue<int> q;
 
    q.push(start);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        if (visit[cur]) continue;
        visit[cur] = 1;
        cout << cur << " ";
 
        for (int i = 0; i < v[cur].size(); i++) {
            if (!visit[v[cur][i]]) q.push(v[cur][i]);
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> N >> M >> start;
    for (int i = 0; i < M; i++) {
        cin >> s >> e;
        v[s].push_back(e);
        v[e].push_back(s);
    }
 
    for (int i = 1; i <= N; i++) sort(v[i].begin(), v[i].end());
 
    dfs(start);
    cout << '\n';
    memset(visit, 0, sizeof(visit));
    bfs(start);
 
    return 0;
}