[백준 / BOJ] 1260 DFS와 BFS

분류: 그래프 탐색

문제: www.acmicpc.net/problem/1260

1260번: DFS와 BFS

• 방문할 수 있는 정점이 여러 개인 경우 정점 번호를 작은 것부터 방문하므로 구현의 편의를 위해 인접행렬을 활용했다.

#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>

#define ll long long
#define INF 1e9

using namespace std;

//https://www.acmicpc.net/problem/1260 DFS와 BFS

int n, m, start;
int ar[1001][1001];
int visit[1001];

void DFS(int start) {
    cout << start << ' ';
    visit[start] = 1;
    for(int i=1; i<=n; i++) {
        if(visit[i]) continue;
        if(ar[start][i]) DFS(i);
    }
}

void BFS(int start) {
    queue<int> q;
    visit[start] = 1;
    q.push(start);
    
    while(q.size()) {
        int cur = q.front();
        q.pop();
        cout << cur << ' ';
        for(int i=1; i<=n; i++) {
            if(visit[i]) continue;
            if(ar[cur][i]) {
                visit[i] = 1;
                q.push(i);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> start;
    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        ar[a][b] = ar[b][a] = 1;
    }
    DFS(start);
    memset(visit, 0, sizeof(visit));
    cout << '\n';
    BFS(start);
    
    return 0;
}