백준 2610 - 회의준비

문제

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

풀이

유니온 파인드와 플로이드 워셜을 활용해 풀이할 수 있는 문제였다.

우선 위원회 구성 조건을 만족하며, 위원회 수를 최대로 만들어야 한다. 이를 위해 유니온
파인드를 활용할 수 있다. 주어지는 간선(지인 관계) 정보를 바탕으로 유니온 연산을 수행해
분리 집합을 만들면, 총 분리 집합 수가 최대 위원회 수가 된다.

이제 각 위원회 내에서 대표로 지정할 사람(노드)를 지정해야 한다. 이 때 그래프 내의
모든 정점간의 최단 이동 거리를 도출하는 플로이드 워셜을 활용할 수 있다. 앞서 간선 정보를
입력받는 과정에서 플로이드 워셜에 사용할 거리 배열에 간선 거리 정보를 반영해준다. 이후,
parent 배열 정보를 바탕으로 분리 집합별로 노드를 모은다. 플로이드 워셜로 갱신한 거리 배열을 이용해 각 노드별로 분리 집합내 다른 노드까지의 최대 거리를 구한다. 이 중 최솟값을 가지는 노드를 대표 노드로 채택한다.

로직의 시간복잡도는 플로이드 워셜의 $O(N^3)$으로 수렴하며 이는 $N=100$인 최악의 경우
에도 무난히 제한 조건 1초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.lang.Integer.parseInt;

public class Main {
    static int[] parent;
    static int[][] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        int m = parseInt(br.readLine());

        parent = new int[n + 1];
        Arrays.fill(parent, -1);

        initDist(n);
        while (m-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());

            dist[u][v] = dist[v][u] = 1;

            int p1 = find(u);
            int p2 = find(v);
            if (p1 == p2) continue;

            if (parent[p1] < parent[p2]) {
                parent[p1] += parent[p2];
                parent[p2] = p1;
            } else {
                parent[p2] += parent[p1];
                parent[p1] = p2;
            }
        }

        floyd(n);

        StringBuilder answer = new StringBuilder();

        // 분리집합별로 부모를 포함한 노드 리스트로 매핑
        Map<Integer, List<Integer>> parentChildMap = IntStream.range(1, parent.length)
                .boxed()
                .collect(Collectors.toMap(Main::find,
                        i -> new ArrayList<>(List.of(i)),
                        (l1, l2) -> {
                            l1.addAll(l2);
                            return l1;
                        }
                ));

        answer.append(parentChildMap.size()).append("\n");

        // 각 분리집합내에서 타 정점까지의 최대 거리가 최소인 노드 탐색
        List<Integer> presidentNodes = parentChildMap.values().stream()
                .map(Main::getPresidentNode)
                .sorted()
                .collect(Collectors.toList());
        presidentNodes.forEach(node -> answer.append(node).append("\n"));

        System.out.print(answer);
        br.close();
    }

    static int getPresidentNode(List<Integer> nodes) {
        int maxDist = Integer.MAX_VALUE;
        int answerNode = -1;

        for (Integer node : nodes) {
            int farDist = -1;

            for (int i = 1; i < dist[node].length; i++) {
                if (dist[node][i] == Integer.MAX_VALUE) continue;

                farDist = Math.max(farDist, dist[node][i]);
            }

            if (maxDist > farDist) {
                maxDist = farDist;
                answerNode = node;
            }
        }

        return answerNode;
    }

    static void floyd(int n) {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][k] == Integer.MAX_VALUE || dist[k][j] == Integer.MAX_VALUE) continue;

                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static void initDist(int n) {
        dist = new int[n + 1][n + 1];
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist[0].length; j++) {
                if (i == j) continue;

                dist[i][j] = Integer.MAX_VALUE;
            }
        }
    }
}

결과