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

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

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

---

• 문제

---

• 문제풀이

먼저, 입력 값을 받아와서 그래프를 초기화한다. 각 정점마다 인접한 정점을 리스트에 추가한다.

그리고, 방문 여부 배열과 정점 방문 순서 배열을 초기화한다. 방문 여부 배열은 모두 false로, 정점 방문 순서 배열은 모두 0자동 설정된다.

다만 여기서는 내림차순으로 방문하기 때문에 배열의 순서를 뒤집어준다.

DFS 함수를 호출합니다. DFS 함수는 재귀적으로 호출되며, 현재 정점을 방문하고 방문 순서를 기록한 뒤 인접한 정점들에 대해서 DFS를 재귀적으로 호출한다.

마지막으로, 정점 방문 순서 배열을 출력한다. 만약 해당 정점이 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

 

---

• 코드 1

namespace YONGYONG2
{
    using System;
    using System.Collections.Generic;
    using System.Text;

    public class Program
    {
        static int N;
        static bool[] DFSbool;
        static bool[] BFSbool;
        static int[] DFSlist;
        static int count = 1;
        static List<int>[] graph;
        public static void DFS(int V)
        {
            if (DFSbool[V])
            {
                return;
            }
            DFSbool[V] = true;
            DFSlist[V] = count;
            count++;
            foreach (int next in graph[V])
            {
                if (!DFSbool[next])
                {
                    DFS(next);
                }
            }
        }
      
        public static void Main(string[] args)
        {
          
            using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
            string[] input = Console.ReadLine().Split(' ');
            N = int.Parse(input[0]);
            int M = int.Parse(input[1]);
            int V = int.Parse(input[2]);
            graph = new List<int>[N + 1];
            for (int i = 1; i <= N; i++)
            {
                graph[i] = new List<int>();
            }

            DFSbool = new bool[N + 1];

            for (int i = 0; i < M; i++)
            {
                string[] line = Console.ReadLine().Split(' ');
                int a = int.Parse(line[0]);
                int b = int.Parse(line[1]);
                graph[b].Add(a);
                graph[a].Add(b);
            }
            for (int i = 1; i <= N; i++)
            {
                graph[i].Sort();
                graph[i].Reverse();
            }


            DFSlist = new int[N + 1];
            
            DFS(V);
            for (int i = 1; i <= N; i++)
            {
               sw.WriteLine(DFSlist[i]);
            }

        }
    }

}

 

---

• 후기

비슷비슷한 문제가 많아서 조금만 고치면 된다.