물 대기

문제

문제 설명

선주는 자신이 운영하는 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)를 의미한다.

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

입출력 예

입력	출력
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0	9

입출력 예 설명

아이디어

제출 코드

package com.example.javacodingtest.boj.gold;

import java.io.*;
import java.util.*;

/*
 @author ranuinclulus
 @since 2024.11.04
 @link https://www.acmicpc.net/problem/1368
 @timecomplex
 @performance 25508kb 304ms
 @category
 @note
 */
public class two1368 {
    class Edge implements Comparable<Edge>{
        int start;
        int end;
        int cost;

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.cost, o.cost);
        }
    }
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder builder = new StringBuilder();
    static StringTokenizer tokenizer;
    static int n;
    static int[] costs, parents;
    static PriorityQueue<Edge> priorityQueue;
    static int minCost;

    public void solution() throws IOException {
        n = Integer.parseInt(reader.readLine());
        costs = new int[n + 1];
        parents = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            costs[i] = Integer.parseInt(reader.readLine());
            parents[i] = i;
        }

        priorityQueue = new PriorityQueue<>();
        for (int i = 1; i <= n; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 1; j <= n; j++) {
                int value = Integer.parseInt(tokenizer.nextToken());
                **if (i == j) priorityQueue.add(new Edge(0, i, costs[i]));
                // 저수지를 설치하는 코드**
                else if (i < j) priorityQueue.add(new Edge(i, j, value));
            }
        }

        while (!priorityQueue.isEmpty()) {
            Edge now = priorityQueue.poll();

            if (find(now.start) == find(now.end)) continue;
            union(now.start, now.end);
            minCost += now.cost;
        }

        builder.append(minCost);
        writer.write(builder.toString());
        writer.flush();
    }

    private void union(int start, int end) {
        int startParent = find(start);
        int endParent = find(end);

        if (startParent < endParent) parents[endParent] = startParent;
        else parents[startParent] = endParent;
    }

    private int find(int node) {
        if (parents[node] == node) return node;
        else return parents[node] = find(parents[node]);
    }

    public static void main(String[] args) throws IOException {
        new two1368().solution();
    }
}