99클럽 코테 스터디 3일차 TIL (플로이드-워셜)

문제

BOJ 2660 - 회장뽑기

해결 방법

1. 친구 관계를 입력받을 때 무방향 그래프처럼 양쪽에 값을 입력해준다.
2. 플로이드-워셜 알고리즘을 사용해 모든 정점을 최솟값 친구 관계로 갱신한다.
3. 각 회원의 최댓값을 구한 후 이 최댓값이 가장 작은 사람이 회장후보로 등록된다.
   • 회원의 점수를 구할 때 총점을 구하는 것이 아닌 회원이 다른 친구들과의 관계 중 최댓값이 그 회원의 점수가 됨을 유의해야 한다.

정답 코드 - JAVA

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[][] graph = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                graph[i][j] = (int)1e9;
            }
        }

        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]);
                }
            }
        }

        int ret = Integer.MAX_VALUE;
        ArrayList<Integer> list = new ArrayList<>();
        int[] arr = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            int max = 0;
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    continue;
                }
                max = Math.max(max, graph[i][j]);
            }
            arr[i] = max;
            ret = Math.min(ret, max);
        }

        for (int i = 1; i <= N; i++) {
            if (arr[i] == ret) {
                list.add(i);
            }
        }

        sb.append(ret).append(" ").append(list.size()).append("\n");
        for (int i : list) {
            sb.append(i).append(" ");
        }
        sb.append("\n");

        bw.write(String.valueOf(sb));
        bw.newLine();
        bw.flush();
    }
}

오늘의 회고

BFS로 풀었던 문제였지만 플로이드-워셜 알고리즘을 적용하니 좀 더 간단히 문제를 해결할 수 있었다.