[BOJ] 10423 - 전기가 부족해

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

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

10423번: 전기가 부족해

난이도: 골드 2

사용언어: JAVA

 

풀이

크루스칼 알고리즘을 사용하는 최소 스패닝 트리 문제입니다. 전형적인 최소 스패닝 트리 문제에 각각의 발전소와의 연결 여부만 추가적으로 확인해 주면 정답을 받을 수 있습니다.

 

각 발전소와의 연결 여부는 각 발전소의 부모와 해당 도시의 부모를 비교해보면 쉽게 구할 수 있겠죠?

 

참고로 각 발전소와의 연결 유무를 확인할 때 2중 반복문을 이용하면 시간 초과가 뜨게 되니 유의하셔야 합니다.

 

import java.io.*;
import java.util.*;
 
class Main {
 
    static class node implements Comparable<node> {
        int a;
        int b;
        int c;
 
        node(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
 
        public int compareTo(node o) {
            return this.c - o.c;
        }
    }
 
    static PriorityQueue<node> pq = new PriorityQueue<>();
    static int[] parent;
    static int[] root;
 
    static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
 
        parent[x] = find(parent[x]);
        return parent[x];
    }
 
    static void union(int a, int b) {
        parent[find(a)] = find(b);
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        parent = new int[N + 1]; // 부모 배열
        root = new int[K]; // 발전소의 번호 배열
 
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i; // 부모 배열 초기화
        }
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            root[i] = Integer.parseInt(st.nextToken());
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
 
 
            pq.add(new node(a, b, c));
        }
 
        int sum = 0; // 총 비용
        while (!pq.isEmpty()) {
            node nd = pq.poll(); // 편의상 연결할 두 도시를 1번 도시와 2번 도시로 호칭
            int a = find(nd.a); // 1번 도시의 부모 업데이트
            int b = find(nd.b); // 2번 도시의 부모 업데이트
 
            if (a == b) { // 연결하고자 하는 두 도시가 이미 연결되어 있는지 체크
                continue;
            }
 
            int flag1 = 0;
            int flag2 = 0;
            for (int i = 0; i < K; i++) { // 각 발전소들과 연결하고자 하는 도시가 연결되어 있는 지 여부
                if (find(root[i]) == a) // 1번 도시와의 각 발전소 연결 여부
                    flag1 = 1;
                if (find(root[i]) == b) // 2번 도시와의 각 발전소 연결 여부
                    flag2 = 1;
            }
 
            if (flag1 == 1 && flag2 == 1) // 둘 다 하나의 발전소라도 연결되어 있다면, 연결을 진행하지 않음
                continue;
 
            union(nd.a, nd.b); // 위에 모두 해당하지 않는다면 두 도시를 연결
            sum += nd.c; // 총 비용에 연결 비용 추가
        }
 
 
        bw.write(String.valueOf(sum));
        bw.flush();
        br.close();
        bw.close();
    }
}