백준 6091 - 핑크 플로이드

문제

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

리뷰

크루스칼을 통해 풀이할 수 있는 문제였다.

각 정점간 최단 경로 비용이 주어진 인접 행렬을 입력받아 MST를 형성하고
이를 인접 리스트의 형태로 표현하는 것이 문제의 요구사항이었다.

답을 도출하기 위해 먼저 인접 행렬 정보를 입력받으며 간선 정보를 비용 기준 최소힙에
저장하고, 크루스칼 로직내에서 List<List<Integer>> 형태로 인접 리스트를 표현한
후, MST 형성시 간선을 채택하며 인접 리스트에 내역을 반영해주어 답을 구했다.

주어질 수 있는 최대 간선 수 $M=N \times (N-1) /2$일 때 크루스칼의 시간 복잡도가
$O(NlogM)$, 구한 인접 리스트를 정렬하며 출력하는 부분의 시간 복잡도가
$O(NMlogM)$이므로 최종적인 시간 복잡도는 $O(NMlogM)$으로 수렴하고 이는
$N=1024$, $M=1024 \times 1023/2$인 최악의 경우에도 무난히 제한 조건 1초를
통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.w));

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

        StringTokenizer st;
        int w;
        for (int u = 1; u < N; u++) {
            st = new StringTokenizer(br.readLine());

            for (int v = u + 1; v < N + 1; v++) {
                w = parseInt(st.nextToken());
                pq.offer(new Edge(u, v, w));
            }
        }

        List<List<Integer>> graph = kruskal(N);
        List<Integer> nodes;
        for (int i = 1; i < graph.size(); i++) {
            nodes = graph.get(i);
            nodes.sort(Comparator.comparingInt(n -> n));
            System.out.print(nodes.size() + " ");
            for (Integer node : nodes) {
                System.out.print(node + " ");
            }
            System.out.println();
        }

        br.close();
    }

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

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

    static boolean union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        if (r1 == r2) return false;

        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }

        return true;
    }

    static List<List<Integer>> kruskal(int N) {
        Arrays.fill(parent, -1);
        List<List<Integer>> graph = new ArrayList<>();
        graph.add(null);
        for (int i = 1; i <= N; i++) graph.add(new ArrayList<>());

        int selected = 0;
        while (!pq.isEmpty() && selected < N - 1) {
            Edge e = pq.poll();

            if (!union(e.u, e.v)) continue;

            selected++;
            graph.get(e.u).add(e.v);
            graph.get(e.v).add(e.u);
        }

        return graph;
    }

    static class Edge {
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과