[백준] 2660 - 회장뽑기 | Java

짱챌·2025년 6월 11일

백준 플로이드-와샬

Algorithm

목록 보기

13/19

📌 문제 정보

[2660: 회장뽑기]

💡 접근 방식

예제 입력을 보고 표를 짜보면 이렇게 된다.

-	1	2	3	4	5
1	0	1	2	2	3
2	1	0	1	1	2
3	2	1	0	2	1
4	2	1	1	0	1
5	3	2	1	1	0

최종적으로 1번의 점수는 3점이고, 2~4번의 점수는 2점, 5번의 점수는 3점이라
회장 후보는 2, 3, 4이다.

즉, 각 회원과의 최단 거리를 구한 후 최대 거리가 최소인 사람을 찾는 문제이다...

회원들의 최단 거리를 구하려면 플로이드 와샬 알고리즘을 사용하면 된다.

✅ 코드

import java.util.*;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static int n;
    static int[][] graph;

    static final int INF = 999_999_999;

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

        n = Integer.parseInt(br.readLine());

        graph = new int[n+1][n+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    graph[i][j] = 0;
                } else {
                    graph[i][j] = INF;
                }
            }
        }


        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (a == -1 && b == -1) {
                break;
            }

            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }

        ArrayList<Integer> find = new ArrayList<>();

        int min = 1_000_000_000;

        for (int i=1; i<=n; i++) {
            int cur = Arrays.stream(graph[i]).max().getAsInt();
            if (min > cur) {
                min = cur;
                find.clear();
                find.add(i);
            } else if (min == cur) {
                find.add(i);
            }
        }

        Collections.sort(find);

        StringBuilder sb = new StringBuilder();
        sb.append(min).append(" ").append(find.size()).append("\n");

        for (Integer i : find) {
            sb.append(i).append(" ");
        }

        System.out.println(sb);

    }

}