[백준][C++] 24480: 알고리즘 수업 - 깊이 우선 탐색 2

 

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

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

 

 

 

 

 

---

- 문제

 

무방향 그래프의 간선들과 시작점 R이 주어지고 내림차순으로 방향이 진행될 때, 각 정점의 방문 순서를 출력하는 문제다.

 

 

---

- 해설

 

1. 가장 먼저 주어진 간선들을 정리해야 한다.

 

- 이차원 배열, vector를 이용해서 각 정점별로 이어지는 간선을 유지한다.

 

2. 각 정점 별로 정렬을 해서 내림차순 혹은 오름차순으로 정점들을 나열한다.

 

3. 방문하지 않은 정점들 위주로 내림차순으로 dfs를 진행한다.

 

 

 

---

- 풀이

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

vector<int> graph[100001];
bool visited[100001] = {false};
int result[100001] = {0};
int cnt = 0;

void dfs(int R)
{
    if (visited[R])
    {
        return;
    }
    visited[R] = true;
    cnt++;
    result[R] = cnt;
    for (int i = 0; i < graph[R].size(); i++)
    {
        dfs(graph[R][i]);
    }
}

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

    int N, M, R, tempX, tempY;
    cin >> N >> M >> R;
    for (int i = 0; i < M; i++)
    {
        cin >> tempX >> tempY;
        graph[tempX].push_back(tempY);
        graph[tempY].push_back(tempX);
    }
    for (int i = 1; i <= N; i++)
    {
        sort(graph[i].begin(), graph[i].end(), greater<int>());
    }
    dfs(R);

    for (int i = 1; i <= N; i++)
    {
        cout << result[i] << '\n';
    }
}

 

 

---

- 새롭게 알게 된 점