백준 163939 - Lost Map

문제

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

리뷰

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

MST를 구성하는 간선들의 정보를 구하여 출력해야 하기 때문에
크루스칼 로직안에서 주어진 간선 정보를 바탕으로 MST를 구성하며
채택된 간선들을 List에 저장하여 반환하는 형식으로 설계하여 답을 구했다.
문제 출력 조건에서 간선의 순서, 정점의 순서에 대해 별다른 조건이 있지 않다.

로직의 시간 복잡도는 크루스칼의 $O(nlogn^2)$으로 수렴하므로 $n=2,500$인
최악의 경우에도 무난히 제한 조건 5초를 통과한다.

간선의 개수는 엄밀히 말해 위 로직에서는 $n^2-n$이다. 자기 자신에 대한 간선을
제외하고 있기 때문에..

코드

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 N;
    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));
        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 = 1; v <= N; v++) {
                w = parseInt(st.nextToken());

                if (u == v) continue;

                pq.offer(new Edge(u, v, w));
            }
        }

        List<Edge> edges = kruskal();
        for (Edge e : edges) {
            System.out.println(e.u + " " + e.v);
        }
        br.close();
    }

    static List<Edge> kruskal() {
        Arrays.fill(parent, -1);
        int selected = 0;
        List<Edge> edges = new ArrayList<>();

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

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

            selected++;
            edges.add(e);
        }

        return edges;
    }

    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 int find(int u) {
        if (parent[u] < 0) return u;

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

    static class Edge {
        int u, v, w;

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

}

결과