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

1. 문제

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

2. 개요

N개 정점, M개 간선으로 이루어진 무방향 그래프가 주어진다.

시작 정점 R이 주어졌을 때, DFS 실행 시 각 정점의 방문 순서를 출력하는 문제.

단, 인접 정점의 방문 순서는 오름차순으로 진행된다.

3. 풀이 및 코드

3-1. 풀이

들어오는 입력대로 그래프를 만들고 방문순서를 카운팅할 변수 cnt를 1로 초기화한다.

visited배열을 만들고, 시작 정점을 cnt로 초기화한다.

그래프의 모든 정점을 돌면서 오름차순 방문이 가능하도록 오름차순 정렬한다.

DFS를 돌면서 미방문 정점을 발견할 때마다 cnt를 1씩 늘리며 이 값으로 visited값을 갱신한다.

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)

def DFS(n):
    global cnt
    graph[n].sort()

    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_24479
{
    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();

            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);
            }
        }
    }
}