[백준] 10423 전기가 부족해 [java]

문제

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

해결 과정

최소 비용으로 간선을 연결 -> MST를 만드는 문제이다.
하지만, 한가지 조건이 더 있는데,
모든 정점이 연결되어야 하는 것이 아니라, 발전소에만 연결되면 된다는 것이다.

핵심 아이디어

발전소를 모두 union하고 시작하면,
모든 발전소에 연결된 것이 모든 정점에 연결된 것처럼 취급될 것이다.

MST에 대해 잘 모르겠다면 -> MST에 관한 글

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static class Graph{
        int vtx1, vtx2, val;

        public Graph(int vtx1, int vtx2, int val) {
            this.vtx1 = vtx1;
            this.vtx2 = vtx2;
            this.val = val;
        }
    }

    public static int find(int[] parent, int num){
        if(parent[num] == num) return num;
        else return find(parent, parent[num]);
    }

    public static void union(int[] parent, int x, int y){
        x = find(parent, x);
        y = find(parent, y);

        int min = Math.min(x, y);
        parent[x] = min;
        parent[y] = min;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int vtxNum = Integer.parseInt(stringTokenizer.nextToken());
        int edgeNum = Integer.parseInt(stringTokenizer.nextToken());
        int powerSupplyNum = Integer.parseInt(stringTokenizer.nextToken());     //발전소 수

        List<Integer> powerList = new ArrayList<>();        // 발전소 리스트

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < powerSupplyNum; i++){
            powerList.add(Integer.parseInt(stringTokenizer.nextToken()));
        }

        List<Graph> partialGraphList = new ArrayList<>();
        for(int i = 0; i < edgeNum; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            int vtx1 = Integer.parseInt(stringTokenizer.nextToken());
            int vtx2 = Integer.parseInt(stringTokenizer.nextToken());
            int edge = Integer.parseInt(stringTokenizer.nextToken());
            partialGraphList.add(new Graph(vtx1, vtx2, edge));
        }

        // 간선 가중치 기준 오름차순 정렬
        Collections.sort(partialGraphList, new Comparator<Graph>() {
            @Override
            public int compare(Graph o1, Graph o2) {
                return o1.val - o2.val;
            }
        });

        // MST에서 정점의 각 부모를 저장하는 배열
        int[] parent = new int[vtxNum + 1];
        for(int i = 0; i < parent.length; i++){
            parent[i] = i;
        }

        for(int i = 1; i < powerList.size(); i++){
            union(parent, powerList.get(i - 1), powerList.get(i));
        }

        int ans = 0;

        for(Graph graph : partialGraphList){
            if(find(parent, graph.vtx1) == find(parent, graph.vtx2)) continue;

            // 두 정점의 부분그래프를 연결함
            union(parent, graph.vtx1, graph.vtx2);
            ans += graph.val;
        }

        System.out.println(ans);
    }
}