백준 7439 - Highways

문제

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

리뷰

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

도시의 정보가 좌표로 주어지고 도시들을 도로로 연결하려할 때, 기존에 지어진
도로에 더해 비용이 최소로 들어가도록 새로 지어지는 도로들의 좌표 정보를 구하는
것이 문제의 조건이었다.

크루스칼을 통해 MST를 형성하며 채택된 도로들의 정보를 저장하는 방식으로
접근하였다. 이 과정에서 비용 기준 최소힙에 도로들의 정보를 저장하였고, 기존에
지어진 도로의 경우 비용을 0으로 하여 최소힙에 저장한 후 도로를 채택하는 과정에서
답을 저장하는 List에 포함시키지 않도록 로직을 구성했다.
모든 도시가 고유한 좌표를 가지므로, 비용이 0인 새로운 도로가 지어질 순 없다

출력 형식과 관련하여 문제에 별다른 조건이 없어, 정렬을 시켜야되나 싶었는데
간선들의 출력 순서는 상관이 없는 것 같다.

로직의 시간 복잡도는 간선의 개수가 $E=M+N\times N-1$일 때 크루스칼의
$O(NlogE)$로 수렴하므로 $N=750$, $E=1000+750\times 749$인 최악의 경우에도
무난히 제한 조건 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.comparingDouble(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];
        int[] px = new int[N + 1];
        int[] py = new int[N + 1];

        StringTokenizer st;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            px[i] = parseInt(st.nextToken());
            py[i] = parseInt(st.nextToken());
        }

        int M = parseInt(br.readLine());
        int u, v;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());

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

        double w;
        for (u = 1; u <= N; u++)
            for (v = 1; v <= N; v++) {
                w = Math.sqrt(Math.pow(px[u] - px[v], 2) + Math.pow(py[u] - py[v], 2));

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

        List<Edge> answer = kruskal(N);
        for (Edge e : answer) {
            int maxVal = Math.max(e.u, e.v);
            int minVal = Math.min(e.u, e.v);
            System.out.println(minVal + " " + maxVal);
        }

        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<Edge> kruskal(int N) {
        Arrays.fill(parent, -1);
        int selected = 0;
        List<Edge> answer = new ArrayList<>();

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

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

            selected++;
            if (e.w == 0) continue;
            answer.add(e);
        }

        return answer;
    }

    static class Edge {
        int u, v;
        double w;

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

결과