[18352] - 특정 거리의 도시 찾기

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

18352번: 특정 거리의 도시 찾기

문제는 쉬운데 오타를 발견 못해 오래걸린 문제..

 

문제 풀이

• 그래프 생성
• 입력받은 단방향 도로를 그래프에 넣기
• 현재 도시가 몇번만에 찾아졌는지 알기위한 번호 배열point_num 생성
• 큐에 시작 도시 삽입, 시작 도시 번호 1
• BFS를 돌며 아직 찾아지지 않았으면(0이면) 큐에 그 도시 넣고, 이전 도시의 번호 +1 해주기
• 도시번호 1번부터 n번까지 돌며 stringbuilder에 번호가 같은 도시 추가

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

namespace Baekjoon.Practice
{
    class _18352
    {
        static void Main(string[] args)
        {
            StringBuilder stb = new StringBuilder();
            //n[0] - 노드 개수, n[1] - 선 개수, n[2] - K, n[3] - 시작
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

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

            for (int i = 0; i < n[1]; i++)
            {
                int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                graph[arr[0]].Add(arr[1]);
            }

            int[] point_num = new int[n[0] + 1];
            Queue<int> q = new Queue<int>();
            point_num[n[3]] = 1;
            q.Enqueue(n[3]);
            while (q.Count > 0)
            {
                int point = q.Dequeue();
                foreach (int i in graph[point])
                {
                    if (point_num[i] == 0)
                    {
                        point_num[i] = point_num[point] + 1;
                        q.Enqueue(i);
                    }
                }
            }

            bool flag = false;
            for (int i = 1; i <= n[0]; i++)
            {
                if (point_num[i]-1 == n[2]) 
                {
                    stb.AppendLine(i.ToString());
                    flag = true;
                }
            }

            if (flag)
                Console.WriteLine(stb);
            else
                Console.WriteLine(-1);
        }
    }
}