[BOJ][C#] 2660 회장뽑기

📕 문제

📌 링크

📗 접근 방식

1. 플로이드-워셜 알고리즘
연결되어 있는 노드는 1로 연결되어 있지 않는 노드는 INF로 설정한 후 플로이드-워셜 알고리즘을 이용하여 모든 노드 쌍 간의 최단 거리를 얻었다.

2. 회장 후보 선정
각 회원에 대해 최대 점수를 계산하고, 이를 scoreArr 배열에 저장한 후 전체 회원 중 최소 점수를 readerScore에 저장하였다.

📘 코드

using System.Text;

namespace BOJ
{
    class No_2660
    {
        const int INF = 987654321;

        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[,] arr = new int[N + 1, N + 1];

            for(int i = 1 ; i <= N ; i++)
                for(int j = 1 ; j <= N ; j++)
                    if(i != j)
                        arr[i, j] = INF;
                    
            while(true)
            {
                string[] input = Console.ReadLine().Split();
                int x = int.Parse(input[0]);
                int y = int.Parse(input[1]);

                if(x == -1 && y == -1)
                    break;

                arr[x, y] = arr[y, x] = 1;
            }

            for(int k = 1 ; k <= N ; k++)
                for(int i = 1 ; i <= N ; i++)                
                    for(int j = 1 ; j <= N ; j++)                    
                        if(arr[i, j] > arr[i, k] + arr[k, j])                        
                            arr[i, j] = arr[i, k] + arr[k, j];
                        
            int readerScore = INF;
            int[] scoreArr = new int[N + 1];

            for(int i = 1 ; i <= N ; i++)
            {
                int score = 0;
                for(int j = 1 ; j <= N ; j++)
                {
                    if(arr[i, j] != INF)
                        score = Math.Max(score, arr[i, j]);
                }

                scoreArr[i] = score;
                readerScore = Math.Min(readerScore, score);
            }

            StringBuilder sb1 = new StringBuilder();
            sb1.Append(readerScore + " ");

            StringBuilder sb2 = new StringBuilder();
            int readerNum = 0;

            for(int i = 1 ; i <= N ; i++)
            {
                if(readerScore == scoreArr[i])
                {
                    readerNum++;
                    sb2.Append(i + " ");
                }
            }

            sb1.Append(readerNum);

            Console.WriteLine(sb1.ToString());
            Console.WriteLine(sb2.ToString());
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 플로이드–워셜