물대기

https://www.acmicpc.net/problem/1368
최소신장 문제 응용 문제
차이점이 있다면 노드 자체에 가중치가 있음
-> 처음에는 자기 자신에게 가는 간선을 추가하려 하였으나 이 방법보다 가상의 노드를 추가하는 것이 쉽다는 것을 깨달음

과정

1. 가상의 노드를 추가한 parents를 만듬
2. 간선을 추가하며 자신의 가중치는 가상의 노드로 향하게 만듬
3. 간선을 가중치 오름차순으로 정렬
4. 나머지는 크루스카 알고리즘과 동일

순서도

https://velog.io/@fruturum/BOJ-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC-hy1m740u
참고

코드

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

public class Main {

    private static int[] parents;
    private static int[][] edges;

    public static void main(final String[] args) throws IOException {
        problem(new InputStreamReader(System.in));
    }

    public static void problem(final InputStreamReader isr) throws IOException {
        init(new BufferedReader(isr));
        System.out.println(kruskal());
    }

    private static void init(final BufferedReader br) throws IOException {
        final int N = Integer.parseInt(br.readLine());
        edges = new int[N * (N+1) / 2 ][];
        parents = new int[N+1];
        for (int i = 0; i < N+1; i++) {
            parents[i] = i;
        }
        for (int i = 0; i < N; i++) {
            edges[i] = new int[]{i,N, Integer.parseInt(br.readLine())};
        }
        int num = N;
        for (int i = 0; i < N; i++) {
            final String[] line = br.readLine().split(" ");
            for (int j = i+1; j < N; j++) {
                edges[num] = new int[]{i,j,Integer.parseInt(line[j])};
                num++;
            }
        }
    }

    private static int kruskal(){
        int result = 0;
        Arrays.sort(edges,(o1, o2) -> o1[2] - o2[2]);
        for (final int[] edge : edges) {
            if (find(edge[0]) != find(edge[1])){
                union(edge[0],edge[1]);
                result += edge[2];
            }
        }
        return result;
    }

    private static void union(final int idx1, final int idx2){
        final int p1 = find(idx1);
        final int p2 = find(idx2);
        if (p1  < p2){
            parents[p2] = p1;
            return;
        }
        parents[p1] = p2;
    }

    private static int find(final int idx){
        if (parents[idx] == idx){
            return idx;
        }
        parents[idx] = find(parents[idx]);
        return parents[idx];
    }
}