그래프를 통한 BFS 연습

간선의 개수 n

도시의 개수 m

 

Seoul Daejeon Daegu Busan Gwangju Cheonan Gongju

 

도시의 간선이 연결되어있는 경우

0 1

0 2

1 3

1 4

2 5

2 6

 

출력

BFS 순서대로 방문하는 도시 번호(영문명) 

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.IO.Pipes;

namespace _230130
{
    class Program
    {
        static int n;
        static int m;
        static int[] visited;
        static int[,] map;
        static int cnt;
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static string[] cityArr;

        static void Main(string[] args)
        {
            n = int.Parse(sr.ReadLine());
            m = int.Parse(sr.ReadLine());

            cityArr = new string[m];
            cityArr = sr.ReadLine().Split(' ');
            visited = new int[n + 1];
            map = new int[n + 1, n + 1];

            for (int i = 0; i < n; i++)
            {
                var arr = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
                map[arr[0], arr[1]] = 1;
                map[arr[1], arr[0]] = 1;
            }

            for (int x = 0; x < n + 1; x++)
            {
                for(int y = 0; y < n + 1; y++)
                {
                    sw.Write("{0} ", map[x, y]);
                }
                sw.WriteLine();
            }

            for(int i = 0; i < n + 1; i++)
            {
                if(visited[i] == 0)
                {
                    cnt++;
                    BFS(i);
                }
            }

            sr.Close();
            sw.Close();
        }

        static void BFS(int x)
        {
            Queue<int> q = new Queue<int>();
            q.Enqueue(x);
            visited[x] = 1;

            while(q.Count > 0)
            {
                x = q.Dequeue();
                sw.Write("{0}({1}) ", x, cityArr[x]);                

                for(int y = 0; y < n + 1; y++)
                {
                    if(map[x, y] == 1 && visited[y] == 0)
                    {
                        q.Enqueue(y);
                        visited[y] = 1;
                    }
                }
            }
        }
    }
}

조금만 더 보면 이해가 될 것 같다.