[C#]백준 18352번: 특정 거리의 도시 찾기

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

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

---

• 문제

---

• 문제풀이

BFS를 시행해주고 각 BFS마다 카운트를 해주어 비교해준다.

 

---

• 코드 1

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

    public class Program
    {
        static int N;
        static int X;
        static int K;
        static bool[] BFSbool;
        static int[] bfscount;
        static bool Print;
        static List<int>[] graph;

        public static void BFS(int V)
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(V);
            BFSbool[V] = true;       
            while (queue.Count > 0)
            {
                int temp = queue.Dequeue();
                foreach (int next in graph[temp])
                {
                    if (!BFSbool[next])
                    {
                        BFSbool[next] = true;
                        queue.Enqueue(next);
                        bfscount[next] = bfscount[temp] + 1;
                        if (bfscount[next] == K)
                        {
                            Print = true;
                        }
                    }
                }
            }
            if (Print)
            {
                for(int i=1;i<N+1;i++)
                {
                    if (bfscount[i] == K)
                    {
                        Console.WriteLine(i);
                    }
                }
            }
            else
            {
                Console.WriteLine(-1);
            }
            }
            public static void Main(string[] args)
            {
                string[] input = Console.ReadLine().Split();
                N = int.Parse(input[0]);
                int M = int.Parse(input[1]);
                K = int.Parse(input[2]);
                X = int.Parse(input[3]);
                graph = new List<int>[N + 1];
                for (int i = 1; i <= N; i++)
                {
                    graph[i] = new List<int>();
                }
                BFSbool = new bool[N + 1];
                bfscount = new int[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[a].Add(b);
                }
                for (int i = 1; i <= N; i++)
                {
                    graph[i].Sort();
                }
                bfscount[X] = 0;
                BFS(X);
            }
        }
    }

 

---

• 후기

카운트를 비교해주는 과정이 어려웠다.