• 문제 설명

간선이 연결된 두 정점의 번호와 탐색을 시작할 번호가 주어졌을 때, DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력해야한다. 방문할 수 있는 정점이 여러 개인 경우, 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우에는 종료한다. (이때 정점 번호는 1번부터 N번까지 이다.)

• 문제 풀이

말 그대로 DFS와 BFS를 구현하면 된다. 일단 graph 변수를 만들어둔 뒤, 각각의 visited 배열과 result(결과) 배열을 만들어주었다.

DFS 함수의 구조로는, 현재 노드에 대해서 방문 처리를 해준다. 그 후, result 배열에 현재 탐색한 노드를 넣어주고, 현재 노드와 연결된 다른 정점을 for문으로 돌려 방문 처리가 안 된 다른 정점들에 대해서 다시 DFS를 돌려준다.

BFS 함수의 구조로는, 똑같이 현재 노드에 대해서 방문 처리를 해주되, Queue를 사용한다.

• 정답 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

vector<vector<int>> graph;
vector<bool> dfs_visited, bfs_visited;
vector<int> dfs_result, bfs_result;

void dfs(int now) {
    dfs_visited[now] = true;
    dfs_result.push_back(now);

    for (auto next : graph[now]) {
        if (!dfs_visited[next]) {
            dfs(next);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    q.push(start);
    bfs_visited[start] = true;

    while (!q.empty()) {
        int now = q.front();
        q.pop();
        bfs_result.push_back(now);

        for (auto next : graph[now]) {
            if (!bfs_visited[next]) {
                bfs_visited[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    FASTIO;

    int n, m, v;
    cin >> n >> m >> v;

    graph.resize(n + 1);
    dfs_visited.resize(n + 1, false);
    bfs_visited.resize(n + 1, false);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

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

    dfs(v);
    bfs(v);

    for (auto x : dfs_result) {
        cout << x << ' ';
    }
    cout << '\\n';

    for (auto x : bfs_result) {
        cout << x << ' ';
    }

    return 0;
}