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

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

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

 

문제 풀이

1. 그래프 구현

2. 깊이 탐색이므로  너비 탐색과 는 다르게, 정점을 방문하지 않았다면 방문하지 않은 정점을 true로 바꾸어 주고, 그 정점을 기준으로 다시 탐색하게 구현

 

너비 탐색

- https://joe0617160.tistory.com/6

[24444] - 알고리즘 수업 - 너비 우선 탐색 1

using System;
using System.Collections.Generic;
using System.Text;

namespace Baekjoon.Silver
{
    class _24479
    {
        static int[] n;
        static Dictionary<int, List<int>> arr;
        static bool[] visited;
        static int[] visit_num;
        static int temp;

        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            arr = new Dictionary<int, List<int>>();

            for (int i = 1; i <= n[0]; i++)
                arr[i] = new List<int>();

            //그래프 구현
            for (int i = 0; i < n[1]; i++)
            {
                int[] point = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                arr[point[0]].Add(point[1]);
                arr[point[1]].Add(point[0]);
            }

            //정렬
            foreach (int k in arr.Keys)
                arr[k].Sort();

            visited = new bool[n[0] + 1];
            visit_num = new int[n[0] + 1];
            temp = 1;
            dfs(n[2]);

            for (int i = 1; i <= n[0]; i++)
                stb.AppendLine(visit_num[i].ToString());

            Console.WriteLine(stb);
        }
        
	//깊이 탐색
        static void dfs(int point)
        {
            visited[point] = true;
            visit_num[point] = temp;
            temp++;

            foreach(int a in arr[point])
            {
                if (!visited[a])
                    dfs(a);
            }
        }
    }
}