플로이드-워셜 (BOJ 회장뽑기)

https://www.acmicpc.net/problem/2660

 

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

public class Main {
    // 모든 노드 간의 최단경로를 구해야 한다 => 플로이드-워셜
    // O(N^3)이지만, N = 50이기 때문에 가능

    static final int INF = 51;

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

        int N = Integer.parseInt(br.readLine());

        int[][] D = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    D[i][j] = 0;
                } else {
                    D[i][j] = INF;
                }
            }
        }

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

            if (A == -1) break;

            // 친구관계는 양방향
            D[A][B] = 1;
            D[B][A] = 1;
        }

        // ----- 입력 끝 -----


        // 플로이드-워셜
        for (int k = 1; k <= N; k++) {         // k = 경유지
            for (int i = 1; i <= N; i++) {     // i = 출발지
                for (int j = 1; j <= N; j++) { // j = 도착지
                    D[i][j] = Math.min(D[i][j], D[i][k] + D[k][j]);
                }
            }
        }


        // 점수 계산
        int[] score = new int[N + 1];
        int minScore = INF;

        for (int i = 1; i <= N; i++) {
            int maxDist = 0;
            for (int j = 1; j <= N; j++) {
                maxDist = Math.max(maxDist, D[i][j]);
            }
            score[i] = maxDist; // 개별 회원의 점수를 계산한다.
            minScore = Math.min(minScore, maxDist); // 최소 점수와 비교한다.
        }


        // 회장 후보 찾기
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            if (score[i] == minScore) {
                list.add(i);
            }
        }


        // 결과 출력
        StringBuilder sb = new StringBuilder();
        sb.append(minScore + " " + list.size() + "\n");
        for (int i : list) {
            sb.append(i + " ");
        }
        System.out.println(sb);
    }
}

 

1. 플로이드-워셜 문제로 판단하는 기준

플로이드-와샬 알고리즘은 모든 노드 간의 최단 경로를 구하는 문제에서 자주 사용됩니다. 이 문제에서 플로이드-워셜을 사용해야 한다는 힌트를 얻을 수 있는 이유는 다음과 같습니다:

• 모든 회원 간의 관계를 고려: 문제에서 각 회원 간의 관계(친구 관계)를 모두 계산해야 하므로, 모든 회원이 서로 얼마나 가까운지 알기 위해 모든 쌍의 최단 경로가 필요합니다.
• "점수" 계산: 점수는 각 회원이 다른 모든 회원과의 거리가 최소인 경로를 찾아야 하며, 최장 거리를 기준으로 점수가 계산됩니다. 이는 각 회원이 다른 모든 회원과의 최단 거리를 구해야 한다는 의미이므로 플로이드-워셜이 적합합니다.
• N이 작음: 문제에서 회원 수가 최대 50명이므로, 시간 복잡도 O(N^3)인 플로이드-워셜 알고리즘을 사용해도 효율적으로 풀 수 있습니다.

 

2. 인접 리스트를 사용하면 안 되는 이유

• 모든 노드 간의 최단 거리를 구하는 문제에서는 인접 행렬을 사용하는 것이 더 자연스럽습니다. 플로이드-워셜 알고리즘은 모든 노드 쌍에 대한 거리를 효율적으로 계산하기 위해 삼중 루프를 사용하며, 이때 인접 행렬에서의 접근이 매우 빠릅니다.
• 인접 리스트는 특정 노드와 직접 연결된 노드들에 대한 정보만 빠르게 얻을 수 있지만, 모든 노드 간의 경로를 탐색할 때는 비효율적일 수 있습니다. 플로이드-워셜은 모든 노드 쌍을 고려하기 때문에 인접 리스트 대신 인접 행렬을 사용하는 것이 계산에 유리합니다.