[BOJ/백준 1260][C++] DFS와 BFS

문제

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

백준 1260

 

문제 내용

그래프에 대한 내용을 입력받고, V번 정점부터 DFS와 BFS를 수행한 결과를 출력하면 된다.

 

문제 풀이

인접리스트 방식으로 문제를 해결해 보았다.

인접 행렬로도 풀릴 것 같기는 한데, 노드가 1000개까지 될 수 있어 인접 행렬을 arr[1001][1001] 이런 식으로 선언을 하게 되면 메모리 초과가 발생할 수도 있을 것 같다. (ide에 제한이 있을 수도 있어서...) 

+) 백준에서 다른 사람 제출 내역을 보니, 인접행렬로 해도 문제를 풀 수 있다. 하지만 언젠가 N이 너무 커질 때를 대비해서 인접 리스트 방식도 알아두면 좋을 것이다.

 

코드

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n, m, v;
vector<int> arr[1001];
int visited[1001];

void dfs(int node) {
    visited[node] = true;
    cout << node << ' ';

    for (auto next : arr[node]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

void bfs() {
    queue<int> q;
    vector<int> visited(n + 1, false);

    q.push(v);
    visited[v] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << ' ';

        for (auto next : arr[node]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

int main() {
    cin >> n >> m >> v;

    int v1, v2;
    for (int i = 0; i < m; i++) {
        cin >> v1 >> v2;

        arr[v1].push_back(v2);
        arr[v2].push_back(v1);
    }

    for (int i = 1; i <= n; i++)
        sort(arr[i].begin(), arr[i].end());

    dfs(v);
    cout << "\n";
    bfs();
}