[알고리즘] 백준 > #2610. 회의준비

문제링크

백준 #2610. 회의준비

풀이방법

같은 위원회 내 모든 사람(정점) 사이의 거리를 계산해야 하기 때문에 플로이드 와샬을 사용했습니다. 문제 풀이의 큰 흐름은 다음과 같습니다!

1. 입력(입력과 동시에 관계가 있는 사람들 사이의 거리를 1로 설정)
2. 모든 구성원 간의 거리를 계산(플로이드와샬 이용)
3. 같은 구성원을 돌며 어떤 사람을 발언자로 했을 때 의사전달시간이 최소가 되는지 확인
4. 결과 출력

사실 플로이드와샬을 이용한다는 생각까지하고 나면 어려울게 없는 문제 였습니다. 하지만 위원회를 구분해 진행하는 부분이 은근 귀찮았어요! 생각한 방법은 크게 두가지 있는데, 실제로 사용한 풀이방법인 첫번째 방법은 위원회에 상관없이 모든 사람 간 거리를 구하고 visited 변수와 거리(MAX_DIST라면 같은 위원회가 아님)를 이용한 방법이었습니다. 다른건 Union-Find 같은 방법을 통해 위원회를 구분한 뒤 그 구성원 간의 거리를 계산, 최소 의사전달시간 구하기 였습니다!

코드

import java.util.*;

public class BOJ2610 {

    static int[][] dist;
    static final int MAX_DIST = 201;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dist[i][j] = (i != j) ? MAX_DIST : 0;
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

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

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

        boolean[] visited = new boolean[n + 1];
        LinkedList<Integer> speakers = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            LinkedList<Integer> attendees = new LinkedList<>();
            if (!visited[i]) {
                for (int j = 1; j <= n; j++) {
                    if (!visited[j] && (dist[i][j] != MAX_DIST)) {
                        attendees.add(j);
                        visited[j] = true;
                    }
                }

                int speaker = attendees.get(0);
                int minOfOutMaxPath = MAX_DIST;
                for (Integer attendee : attendees) {
                    int maxPath = 0;
                    for (int j = 1; j <= n; j++) {
                        if (dist[attendee][j] != MAX_DIST && maxPath < dist[attendee][j]) maxPath = dist[attendee][j];
                    }

                    if (minOfOutMaxPath > maxPath) {
                        speaker = attendee;
                        minOfOutMaxPath = maxPath;
                    }
                }

                speakers.add(speaker);
            }
        }

        Collections.sort(speakers);
        StringBuilder result = new StringBuilder();
        result.append(speakers.size() + "\n");
        for (Integer speaker : speakers) result.append(speaker + "\n");

        System.out.print(result.toString());
    }
}