BOJ 1260 - DFS와 BFS

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

그래프를 DFS와 BFS로 탐색한 후에 출력하는 프로그램을 작성하시오.

Solution

• 정점의 개수와 정점끼리의 연결정보를 input으로 받는다.

• 그 후 DFS와 BFS로 탐색결과를 출력한다.

• 방문 가능한 정점이 2개 이상일시 작은 숫자로 방문한다.

• 그래프의 구현은 인접리스트로 구현하였다.

#include <bits/stdc++.h>
using namespace std;

void dfs(int x);
void bfs(int x);

vector<int> a[1001]; // 인접리스트
bool check[1001];
int v, e, s; // 정점 개수, 간선 개수, 시작점

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> v >> e >> s;

    //정점들끼리의 정보를 입력받고 저장함.
    for (int i = 0; i < e; i++) {
        int n1, n2;
        cin >> n1 >> n2;
        a[n1].push_back(n2);
        a[n2].push_back(n1);
    }

    for (int i = 1; i <= v; i++) {
        sort(a[i].begin(), a[i].end()); //작은 숫자부터 방문하기 위해서
    }

    dfs(s); cout << '\n';
    memset(check, false, sizeof(check)); //check 배열 초기화
    bfs(s); cout << '\n';
    return 0;
}

//DFS
void dfs(int x) {
    check[x] = true; //정점을 방문
    cout << x << ' '; // 정점 방문 출력
    for (int i = 0; i < a[x].size(); i++) {
        int next = a[x][i]; // 연결되어있는 정점 방문
        if (check[next] == false) //아직 방문하지 않은 점이라면 
            dfs(next); // 재귀로 방문
    }
}

//BFS
void bfs(int x) {
    queue<int> q;
    check[x] = true; //정점을 방문
    q.push(x); // 방문한 점은 큐에 넣는다. (방문과 같은 의미)

    while (!q.empty()) {
        int node = q.front(); //q.front()가 현재 위치한 정점.
        q.pop();
        cout << node << ' ';

        for (int i = 0; i < a[node].size(); i++) {
            int next = a[node][i];
            if (check[next] == false) { //방문하지 않은 점이라면
                check[next] = true; // 방문
                q.push(next); // 그리고 큐에 넣기! (방문과 push는 동시에 이뤄짐)
            }
        }
    }
}