[BOJ] C++ 24480 알고리즘 수업 - 깊이 우선 탐색 2 - DFS, 정렬

예제 입력 1

5 5 1
1 4
1 2
2 3
2 4
3 4

예제 출력 1

1
4
3
2
0

 

 

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

---

 무방향 그래프를 구현하고 오름차순으로 DFS를 구현한 뒤 정점들에 대한 방문 순서를 차례로 출력하면 되는 문제이다. DFS의 기본 이론은 시작 정점에 대해 방문할 수 있는 정점 중 정해진 기준(문제에서는 오름차순)에 따라 방문하고, 다시 방문한 정점에 대해 방문할 수 있는 정점 중 기준에 따라 반복하는 것을 반복하는 것이다. 방문할 수 있는 정점이 없다면 전에 방문한 정점으로 돌아가서 다음 정점으로 방문하면 된다. 따라서 주로 재귀적으로 구현한다.

 

 먼저 그래프를 벡터 배열로 구현하여 동적 배열로 간선을 나타내었다. 그리고 DFS 수행을 위한 정점의 방문 여부를 나타내는 visited 부울 벡터와 답을 저장할 res 벡터를 구현하였고 이들을 이용해 DFS를 수행하였다. 기준이 오름차순 이므로 그래프 구현 후 간선들을 오름차순으로 정렬하여 순서대로 방문하였다. 

 

 구현할 때 주의할 점은 벡터들을 함수에서도 이용해야 하므로 전역 변수로 선언하면 편하다는 점과 벡터 배열로 동적 배열을 구현하는 부분이었다. 벡터 배열을 처음 다룬다면 조금 헷갈릴 수 있다. vector <int> G [N];과 같이 사용할 수 있는데, 이 말이 뭐냐면 사이즈가 정해지지 않은 벡터를 N개 만들어 주세요~라는 뜻이다. 그 후 G[i].push_back(x);와 같은 방식으로 i번째 벡터의 가장 뒤에 원소 x를 넣는 식으로 사용할 수 있고, i번째 벡터는 이차원 배열의 i행에 해당한다. 예제의 그래프를 벡터 배열로 나타내면 아래와 같다.

/** 정렬 24479 깊이 우선 탐색 1 **/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 정점의 수 N, 간선의 수 M, 정답을 마킹할 때 쓸 cnt 변수 선언
int cnt = 2, N, M;
// 정답 및 그래프 벡터 구현
vector<int> res(100001, 0), G[100001];
// 방문 여부 확인 벡터 구현
vector<bool> visited(100001, false);

void dfs(int R)
{
    visited[R] = true;
    for (int i = 0; i < G[R].size(); i++)
    {
        // 정점 R의 i번째 간선이 방문하지 않았다면 방문.
        if (!visited[G[R][i]])
        {
            visited[G[R][i]] = true;
            res[G[R][i]] = cnt++;
            dfs(G[R][i]);
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int M, R;
    cin >> N >> M >> R;

    // 그래프 구현 후 간선 오름차순으로 정렬
    while (M--)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i < N + 1; i++)
        sort(G[i].begin(), G[i].end());

    res[R] = 1;

    // dfs 수행
    dfs(R);

    for (int i = 1; i < N + 1; i++)
        cout << res[i] << "\n";
}