문제링크

풀이

문제를 다 읽어보면, 점수가 가장 작은 사람이 회장이 된다는 문장이 약간 어색하다. 점수가 제일 작은데 왜 회장이지? 하지만 결국엔 점수가 작다는 것은 모든 회원들과 가장 가까운 관계를 가지고 있다는 것을 의미한다.
모임의 각 회원의 점수를 구해야하는데, 점수는 곧 가장 가깝지 않은 회원과의 거리가 된다.
따라서 각 회원마다 다른 모든 회원까지의 거리를 구하고 그 중에서 최댓값을 구하면 점수가 된다.
그리고 가장 작은 점수를 구하고 그 점수에 해당하는 회원 수와 회원 번호를 구하면 된다.

플로이드와샬알고리즘을 활용하여 풀이하였다.

• 직접적으로 연결되지 않는 관계를 따로 표현해야하므로 이차원배열을 기본적으로 51으로 초기화해주었다. (회원 수가 최대 50명이기 때문에 51로 설정했지만, 적당히 더 큰 수여도 상관은 없다.)
  • 근데 여기서 주의해야할 점이 있다. 처음에 51이 아닌 Integer.MAX_VALUE로 설정을 하였더니, 플로이드와샬을 돌리고 나니 값들이 매우 이상하게 나왔다. 그 이유는 아무래도 정수 최댓값들을 더하는 경우(아래 코드에서 graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);)에 해당할 경우 오버플로우가 발생하기 때문이다.
• 입력으로 주어지는 관계는 양방향으로 거리 1로 초기화해준다.
• 플로이드와샬 알고리즘을 사용해서 모든 회원으로부터 모든 회원까지의 최단 거리를 업데이트한다. 문제에 주어진 입력을 예로 들면 아래와 같은 상태가 된다.

• 회원번호가 1부터 시작하므로 인덱스가 0인 행과 열은 사용하지 않는다.

• 각 회원마다 관계가 가장 먼 거리가 점수이다.

  • 첫번째 행은 회원번호 1과 나머지 회원과의 거리를 뜻한다.
  • 2번과는 친구사이, 3번과는 친구의 친구사이, 4번과는 친구의 친구사이, 5번과는 친구의 친구의 친구 사이 인 것이다.

• 이제 각 회원들의 점수를 배열에 저장하면 아래와 같다.

  1번	2번	3번	4번	5번
  3	2	2	2	3

• 여기서 최소값인 2가 회장 후보의 점수가 되고 2번, 3번, 4번이 회장 후보가 되는 것이다.

⚠️ 주의할 점
코드에서 확인하면 알 수 있겠지만, 플로이드와샬 메서드에서 i와 j가 같은 경우에는 0을 넣었다. 이렇게 하지 않으면 i, j가 같은 경우 즉, 자기 자신과의 관계를 거리 2로 계산하게 된다.

위 상황을 고려하지 못해서 첫번째 시도는 틀렸고, 질문 게시판에 다른 분이 올려주신 반례를 통해 해결하였다.
반례

2
1 2
-1 -1

정답 
1 2
1 2

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol2660 {
    static int[] memberDepth;
    static int n;
    static int[][] graph;
    static int INF = 51;
    static int score;
    static int count = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        memberDepth = new int[n + 1];
        graph = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                graph[i][j] = INF;
            }
        }

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            if (from == -1 && to == -1) {
                break;
            }
            graph[to][from] = 1;
            graph[from][to] = 1;
        }


        floyd();

        for (int i = 1; i <= n; i++) {
            memberDepth[i] = findMax(graph[i]);
        }

        score = findMin(memberDepth);
        System.out.print(score + " ");
        for (int i = 1; i <= n; i++) {
            if (memberDepth[i] == score) {
                count++;
            }
        }
        System.out.println(count);
        for (int i = 1; i <= n; i++) {
            if (memberDepth[i] == score) {
                System.out.print(i + " ");
            }
        }
    }

    public static void floyd() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j) {
                        graph[i][j] = 0;
                    }
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }

    public static int findMax(int[] arr) {
        int max = -1;
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }

    public static int findMin(int[] arr) {
        int min = 100;
        for (int i = 1; i < arr.length; i++) {
            min = Math.min(min, arr[i]);
        }
        return min;
    }
}