[BaekJoon] 1368 물대기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] wellCosts, parents;
    static PriorityQueue<Edge> edges;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        edges = new PriorityQueue<>();
        wellCosts = new int[N + 1];
        parents = new int[N + 1];
        for(int idx = 1; idx <= N; idx++) {
            int makeCost = scanner.nextInt();

            wellCosts[idx] = makeCost;
            parents[idx] = idx;
        }

        for(int start = 1; start <= N; start++) {
            for(int end = 1; end <= N; end++) {
                int cost = scanner.nextInt();

                if(start == end) edges.add(new Edge(0, start, wellCosts[start]));
                else edges.add(new Edge(start, end, cost));
            }
        }
    }

    static void solution() {
        System.out.println(kruskal());
    }

    static int kruskal() {
        int count = 0, totalCost = 0;
        while(count < N) {
            Edge cur = edges.poll();
            int start = cur.start, end = cur.end, cost = cur.cost;

            if(!isSameParent(start, end)) {
                union(start, end);
                count++;
                totalCost += cost;
            }
        }

        return totalCost;
    }

    static int findParent(int ricePaddy) {
        if(ricePaddy == parents[ricePaddy]) return ricePaddy;
        return parents[ricePaddy] = findParent(parents[ricePaddy]);
    }

    static void union(int ricePaddy1, int ricePaddy2) {
        int parent1 = findParent(ricePaddy1), parent2 = findParent(ricePaddy2);

        if(parent1 != parent2) {
            if(parent1 < parent2) parents[parent2] = parent1;
            else parents[parent1] = parent2;
        }
    }

    static boolean isSameParent(int ricePaddy1, int ricePaddy2) {
        int parent1 = findParent(ricePaddy1), parent2 = findParent(ricePaddy2);
        return parent1 == parent2;
    }

    static class Edge implements Comparable<Edge> {
        int start, end, cost;

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


        @Override
        public int compareTo(Edge e) {
            return cost - e.cost;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 각 논 사이를 연결하는데 드는 비용이 낮은 순으로 싸이클이 생기지 않게 N - 1개의 경로를 선택하여 논들을 연결하면 최소 비용이 됩니다.
• 그런데, 이 문제에서는 최소 하나의 논에는 우물을 파야하기 때문에 단순히 경로만 지정하는 것이 아니라 우물을 팔 논도 선택해야 합니다.
• 그러므로 실제로는 존재하지 않는 0번 논부터 각 논까지 연결하는 경로를 추가하고 그 때의 비용을 각 논에 우물을 파는 데에 필요한 비용으로 설정합니다.
• 이렇게 추가한 경로까지 이용하여 경로를 선택하는데, 0번 논이 추가되어 총 N개의 경로를 싸이클이 생기지 않게 선택합니다.
• 0번 논에서 어떠한 논으로 연결된 경로는 해당 논에 우물을 판다는 의미이고, 나머지 N - 1개의 경로를 이용해 논들을 연결한다면 논들을 연결하는 최소 비용이 됩니다.