[BOJ/C++] DFS와 BFS(1260번)

1. 개요

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

1260번: DFS와 BFS

1-1. 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성한다. 방문할 수 있는 정점이 여러개 일 시, 정점 번호가 작은것을 먼저 방문하고 더이상 방문할 수 없는 경우 종료한다. 

1-2. 제한 사항

 - 첫 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V가 주어짐

 - N은 1 이상 1,000 이하, M은 1 이상 10,000 이하

 - 다음 M개 줄에는 간선이 연결하는 두 정점 번호가 주어짐

---

2. 구현

2-1. 풀이

우리가 흔히 알고 있는 BFS, DFS 방식을 각각 구현하여 풀면 된다. DFS를 단순히 배열 stack을 생성하여 풀이를 진행하니, out of bounds 에러가 떠서 재귀 방식으로 구현하였다. BFS, DFS 자체는 구현하기 어렵지 않았지만 런타임 에러가 조금 자주떠서 헤맸었다.

2-2. 코드

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

constexpr size_t MAX_NUM = 1001;
vector<int> nums[MAX_NUM];

bool visited[MAX_NUM];
int queue[MAX_NUM]; 

int N, M, V, a, b;

void DFS(int cur);
void BFS();

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

    cin >> N >> M >> V;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        nums[a].push_back(b);
        nums[b].push_back(a);
    }

    for (int i = 0; i <= N; i++) {
        sort(nums[i].begin(), nums[i].end());
    }

    DFS(V);
    cout << "\n";
    fill(visited, visited + N + 1, false);
    BFS();

    return 0;
}

void DFS(int cur) {
    if (visited[cur]) return;
    cout << cur << ' ';
    visited[cur] = true;
    for (int i = 0; i < nums[cur].size(); i++) {
        DFS(nums[cur][i]);
    }
}

void BFS() {
    int front = -1, rear = -1;
    queue[++front] = V;
    while (front != rear) {
        int cur = queue[++rear];
        visited[cur] = true;
        cout << cur << ' ';
        for (int i = 0; i < nums[cur].size(); i++) {
            if (!visited[nums[cur][i]]) {
                queue[++front] = nums[cur][i];
                visited[nums[cur][i]] = true;
            }
        }
    }
}