[백준] 10423번 : 전기가 부족해

10423번: 전기가 부족해

---

[크루스칼 알고리즘]

보통 MST하면 모든 정점이 하나의 덩어리로 연결되는 것을 생각할 수 있는데, 이 문제의 경우 발전소의 개수(k)개의 덩어리로 나뉘어 모든 정점이 연결되었을 때의 합을 출력하는 문제이다.

 

나는 유니온-파인드 부분을 수정했다. 보통 유니온-파인드는 두 정점 a, b를 받아 더 작은 번호를 부모 노드로 삼는 것이 일반적인데, Set에 발전소의 번호를 넣어두고

1) 두 정점 모두 발전소에 연결되어있지 않다면?

- 일반적인 유니온-파인드

 

2) 두 정점 중 한 곳에 발전소와 연결된 곳이 있다면?

- 부모노드의 번호는 그 발전소의 번호

 

3) 두 정점 모두 발전소에 연결되어있다면? (동일한 발전소든 서로 다른 발전소든 상관없이)

- 연결하지 않는다

코드로 보면 조금 더 이해가 쉬울 것이다.

    static int[] parent = new int[1001];

    static int getParent(int x){
    
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }
    
    static boolean findParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(set.contains(a) && set.contains(b)) return true; //둘 다 발전소에 연결되어있으면 따로 연결할 필요 X

        return a == b;
    }
    
    static void unionParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(!set.contains(a) && !set.contains(b)){ //두 정점 모두 발전소와 떨어져있을 때
            if(a < b)
                parent[b] = a;
            else
                parent[a] = b;
        }
        //둘 중 한곳에 발전소와 연결되어있을 때
        else if(set.contains(a) && !set.contains(b))
            parent[b] = a;
        else if(!set.contains(a) && set.contains(b))
            parent[a] = b;
    }

위의 Union-Find부분만 잘 이해한다면 나머지는 일반적인 크루스칼 알고리즘과 동일하다.

# Code </>

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

public class Main {

    static class Edge implements Comparable<Edge>{
        int h, tg, d;
        public Edge(int home, int target, int dist){
            h=home;
            tg=target;
            d=dist;
        }
        @Override
        public int compareTo(Edge o) {
            return d - o.d;
        }
    }

    static Set<Integer> set = new HashSet<>();
    static List<Edge> list = new ArrayList<>();
    static int[] parent = new int[1001];

    static int getParent(int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }
    static boolean findParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(set.contains(a) && set.contains(b)) return true;

        return a == b;
    }
    static void unionParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(!set.contains(a) && !set.contains(b)){
            if(a < b)
                parent[b] = a;
            else
                parent[a] = b;
        }
        else if(set.contains(a) && !set.contains(b))
            parent[b] = a;
        else if(!set.contains(a) && set.contains(b))
            parent[a] = b;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++) parent[i] = i;

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<k; i++) set.add(Integer.parseInt(st.nextToken()));

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int tg = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            list.add(new Edge(h, tg, d));
            list.add(new Edge(tg, h, d));
        }

        Collections.sort(list);

        int sum = 0;
        for(Edge e: list){
            if(!findParent(e.h, e.tg)){
                unionParent(e.h, e.tg);
                sum += e.d;
            }
        }
        System.out.println(sum);
    }
}