[24445] - 알고리즘 수업 - 너비 우선 탐색 2

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

24445번: 알고리즘 수업 - 너비 우선 탐색 2

 

https://joe0617160.tistory.com/6

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

풀이방법

위 24444번 문제에서 내림차순으로 정렬하고 제출하면 될줄 알았는데, 런타임에러(Execption)이 떠서, 그래프 구현 코드를 수정 하였다.

24444번에서는 사전에 키가 존재 하지 않으면 그 키에 대해 리스트값을 생성해 주었는데, 24445번에서는 시작부터 정점의 수 만큼 리스트를 먼저 생성해 주고, 각 키에 해당하는 값들을 add해주었다.

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

namespace Baekjoon.Silver
{
    class _24445
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            Dictionary<int, List<int>> 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();
                arr[k].Reverse();
                //Console.Write(k + " : ");
                //Console.WriteLine(string.Join(" ", arr[k]));
            }

            bool[] visited = new bool[n[0] + 1];
            int[] visit_num = new int[n[0] + 1];
            visit_num[n[2]] = 1;
            int temp = 1;
            Queue<int> que = new Queue<int>();

            que.Enqueue(n[2]);
            visited[n[2]] = true;

            //bfs
            while (que.Count > 0)
            {
                int num = que.Dequeue();
                foreach (int a in arr[num])
                {
                    if (!visited[a])
                    {
                        visited[a] = true;
                        que.Enqueue(a);
                        temp++;
                        visit_num[a] = temp;
                    }
                }
            }

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

            Console.WriteLine(stb);
        }
    }
}