[백준 / C#] 1389 : 케빈 베이컨의 6단계 법칙

internal class Program
    {
        static int[,] arr;
        static int n, m, start, end, min = int.MaxValue, result = 0;
        static List<List<int>> list = new List<List<int>>();
        static bool[] visit = new bool[101];
        static void BFS(int pivot, int cnt)
        {
            if(pivot == end)
            {
                arr[start, end] = Math.Min(cnt, arr[start, end]);
                return;
            }
            visit[pivot] = true;
            for (int i = 0; i < list[pivot].Count; i++)
            {
                if (!visit[list[pivot][i]])
                {
                    BFS(list[pivot][i], cnt + 1);
                    visit[list[pivot][i]] = false;
                }
            }
        }
        static void Solution()
        {
            for (int i = 1; i <= n; i++)
            {
                start = i;
                for (int j = 1; j <= n; j++)
                {
                    end = j;
                    if (list[i] != null)
                    {
                        visit[i] = true;
                        BFS(start, 0);
                        visit[i] = false;
                    }
                }
                int sum = 0;
                for (int num = 1; num <= n; num++)
                    sum += arr[i, num];
                if (sum < min)
                {
                    min = sum;
                    result = i;
                }
            }
        }
        static void Input()
        {
            var input = Console.ReadLine().Split();
            n = int.Parse(input[0]);
            m = int.Parse(input[1]);
            arr = new int[n + 1, n + 1];
            for (int i = 0; i <= n; i++)
            {
                list.Add(new List<int>());
                for (int j = 0; j <= n; j++)
                    arr[i, j] = int.MaxValue;
            }
            for(int i=0; i<m; i++)
            {
                input = Console.ReadLine().Split();
                list[int.Parse(input[0])].Add(int.Parse(input[1]));
                list[int.Parse(input[1])].Add(int.Parse(input[0]));
            }
        }
        static void Output()
        {
            Console.WriteLine(result);
        }
        static void Solve()
        {
            Input();
            Solution();
            Output();
        }
        static void Main(string[] args)
        {
            Solve();        
        }
    }