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

1. 문제

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

2. 개요

N개 정점, M개의 간선을 가지는 그래프를 R번 정점부터 DFS로 순회했을 때, 각 정점의 방문 순서를 출력하는 문제. (인접 정점의 방문 순서는 내림차순)

3. 풀이 및 코드

3-1. 풀이

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

[백준] 24479 - 알고리즘 수업 - 깊이 우선 탐색 1

오름차순 방문이 내림차순 방문으로 바뀐 점만 빼면 24479번 문제와 완전히 똑같다.

그래프를 입력에 맞게 만들고 내림차순 방문이 가능하도록 정렬하면서 DFS를 진행한다.

3-2. Python

import sys

sys.setrecursionlimit(100000000)

N, M, R = map(int, sys.stdin.readline().split())

graph = [[] for i in range(N + 1)]
visited = [0 for i in range(N + 1)]
visited[R] = 1
cnt = 1

for i in range(M):
    s, e = map(int, sys.stdin.readline().split())

    graph[s].append(e)
    graph[e].append(s)

for i in range(N + 1):
    graph[i].sort(reverse = True)

def DFS(n):
    global cnt

    for nxt in graph[n]:
        if visited[nxt] != 0:
            continue

        cnt += 1
        visited[nxt] = cnt
        DFS(nxt)

DFS(R)

for i in range(1, N + 1):
    print(visited[i])

3-3. C#

namespace boj_24480
{
    internal class Program
    {
        static List<int>[] graph;
        static int[] visited;
        static int cnt;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int N = int.Parse(input[0]), M = int.Parse(input[1]), R = int.Parse(input[2]);

            graph = new List<int>[N + 1];

            for (int i = 0; i < N + 1; i++)
                graph[i] = new();

            visited = new int[N + 1];

            for (int i = 0; i < M; i++)
            {
                input = sr.ReadLine().Split();

                int s = int.Parse(input[0]), e = int.Parse(input[1]);

                graph[s].Add(e);
                graph[e].Add(s);
            }

            visited[R] = 1;
            cnt = 1;

            for (int i = 0; i < N + 1; i++)
                graph[i].Sort((x, y) => y - x);

            DFS(R);

            for (int i = 1; i < N + 1; i++)
                sw.WriteLine(visited[i]);

            sw.Close();
        }

        static void DFS(int n)
        {
            foreach (int nxt in graph[n])
            {
                if (visited[nxt] != 0)
                    continue;

                visited[nxt] = ++cnt;
                DFS(nxt);
            }
        }
    }
}