[ BOJ ][JAVA][1368] 물대기

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

1368번: 물대기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	536	213	163	40.148%

문제

선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.

각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.

입력

첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i = 0)를 의미한다.

출력

첫 줄에 모든 논에 물을 대는데 필요한 최소비용을 출력한다.

예제 입력 1

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

예제 출력 1

9

코드

/*
    물대기
    논 사이 연결 vs 논에 우물 파기
    직접 우물을 파는 경우 0번 노드(가상의 노드)에 연결하는 간선을 만들고 직접 우물을 파는 비용을 추가하여 MST를 완성한다.
    크루스칼, MST(Union-Find)
*/
import java.io.*;
import java.util.*;
public class p1368 {
    static class Edge implements Comparable<Edge> {
        int s, e, cost;
        public Edge (int s, int e, int cost) {
            this.s = s;
            this.e = e;
            this.cost = cost;
        }
        public int compareTo(Edge o) {
            return cost - o.cost;
        }
    }
    static int n;
    static int[] w, parent, rank;
    static int[][] p;
    static PriorityQueue<Edge> pq = new PriorityQueue<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        w = new int[n + 1];
        parent = new int[n + 1];
        rank = new int[n + 1];
        p = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int i = 1; i <= n; i++) {
            w[i] = Integer.parseInt(br.readLine());
        }
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                p[i][j] = Integer.parseInt(st.nextToken());

                // *핵심* 여기서 가상의 노드 0을 만들고 0과 연결된 간선은 우물을 파는 비용으로 해야 한다
                if (i != j) pq.add(new Edge(i, j, p[i][j]));
                else pq.add(new Edge(0, i, w[i]));

            }
        }

        mst();
    }
    static void mst() {
        int ret = 0;
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int u = edge.s;
            int v = edge.e;
            if (find(u) == find(v)) continue;
            union(u, v);
            ret += edge.cost;
        }
        System.out.println(ret);
    }

    static void union(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v) {
            if (rank[u] < rank[v]) {
                parent[u] = v;
            } else {
                parent[v] = u;
                if (rank[u] == rank[v]) {
                    rank[u]++;
                }
            }
        }
    }
    static int find(int x) {
        if (x == parent[x]) return x;

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