99클럽 코테 스터디 3일차 TIL [플로이드-워샬 알고리즘]

- 오늘의 학습 키워드 : 플로이드-워샬 알고리즘
[문제 이름 : 회장뽑기 (백준 2660, G5)]
문제 url : https://www.acmicpc.net/problem/2660

내가 작성한 코드는 아래와 같다.

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

 class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] graph = new int[n + 1][n + 1];

        // 무한대 값으로 초기화
        for (int i = 1; i <= n; i++) {
            Arrays.fill(graph[i], 1000); // 충분히 큰 값으로 초기화
            graph[i][i] = 0; // 자기 자신까지의 거리는 0
        }

        // 관계 입력
        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++) {
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }

        int[] scores = new int[n + 1];
        int minScore = Integer.MAX_VALUE;

        // 회원 점수 계산
        for (int i = 1; i <= n; i++) {
            int maxDistance = 0;
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    maxDistance = Math.max(maxDistance, graph[i][j]);
                }
            }
            scores[i] = maxDistance;
            minScore = Math.min(minScore, maxDistance);
        }

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

        // 출력
        System.out.println(minScore + " " + candidates.size());
        for (int candidate : candidates) {
            System.out.print(candidate + " ");
        }
    }
}

[풀이 과정] - (풀이 시간: 1시간)
1. 회원 간의 관계를 인접 행렬로 나타낸다. 이때, 모든 회원 간의 거리를 무한대(1000)로 초기화하고, 자기 자신은 0으로 설정한다.
2. 친구 관계에 따라 직접 연결된 친구들 간의 거리를 1로 저장한다.
3. 플로이드-와샬 알고리즘을 사용해 각 회원 쌍 간의 최단 거리를 계산한다. 중간 회원 k를 거쳐 i -> j로 가는 경로와 i -> j의 기존 경로를 비교하여 더 짧은 경로를 graph[i][j]에 업데이트한다.
4. 각 회원의 점수는 해당 회원에서 다른 모든 회원까지의 최단 거리 중 가장 큰 값이다. scores[i]에 회원 i의 점수를 저장하고, 모든 회원의 점수 중 최솟값을 minScore에 저장한다.
5. minScore와 동일한 점수를 가진 회원들을 회장 후보로 선정한다. candidates 리스트에 회장 후보들을 추가한다.
6. 최소 점수, 후보의 수, 회장 후보들의 번호를 출력한다.

내일은 OS 전공 과목에 대해 공부할 예정이다.