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

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

 

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

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

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

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

---

1.  아이디어

 

도시를 노드, 케이블을 간선으로 하는 최소 스패닝 트리들로 구성시키는 문제로 각 최소 스패닝 트리에 발전소가 하나만 있게 해야한다. 이를 위해 각 최소 스패닝 트리의 그룹장이 항상 발전소가 되도록 크루스칼 알고리즘으로 구현했다.

---

2. 문제풀이

 

발전소가 위치한 도시는 Set에 별도로 저장한 후 크루스칼 알고리즘을 사용했다. 크루스칼 알고리즘에서 해당 케이블에 연결된 두 도시의 그룹장을 뽑아서 둘이 일치하거나(싸이클이 생김) 둘 다 발전소가 설치됐으면 넘어가고 한쪽만 발전소가 설치됐으면 발전소가 설치된 쪽이 그룹장이 되도록 유니온을 했다. 둘 다 발전소가 설치가 안됐으면 아무쪽이나 연결해도 된다.(간선 선택이 끝나면 발전소가 설치된 최소 스패닝 트리와 결국 연결됨) 이후 케이블이 (도시의 수 - 1) - (발전소가 설치된 도시의 수 - 1)이 되면 주어진 도시들이 최소 스패닝 트리들로 모두 연결되게 된다.

---

3. 코드

 

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

public class Main {

    private static class Edge implements Comparable<Edge> {
        int a;
        int b;
        int w;

        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.w, o.w);
        }
    }

    private static int[] p;

    private static int[] make(int N) {
        int[] arr = new int[1 + N];
        for (int i = 1; i <= N; i++) arr[i] = i;
        return arr;
    }

    private static int find(int x) {
        if (x == p[x]) return x;
        return p[x] = find(p[x]);
    }

    private static void union(int x, int y) {
        p[find(y)] = find(x);
    }

    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());

        // 발전소가 설치된 도시 저장
        Set<Integer> set = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            set.add(Integer.parseInt(st.nextToken()));
        }

        PriorityQueue<Edge> edges = new PriorityQueue<>();
        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 W = Integer.parseInt(st.nextToken());
            edges.add(new Edge(A, B, W));
        }

        int ans = kruskal(N, edges, set);
        System.out.println(ans);
    }

    private static int kruskal(int N, PriorityQueue<Edge> edges, Set<Integer> set) {
        p = make(N);

        int sum = 0;
        int cnt = 0;

        while (!edges.isEmpty()) {
            Edge e = edges.remove();
            int fa = find(e.a);
            int fb = find(e.b);

            if (fa == fb) continue;

            // 두 도시의 조상이 모두 발전소면 연결 X
            if (set.contains(fa) && set.contains(fb)) continue;

            // 발전소가 조상이 되도록 유니온
            if (set.contains(fa)) union(e.a, e.b);
            else union(e.b, e.a);

            sum += e.w;
            cnt++;

            if (cnt == N - 1 - (set.size() - 1)) return sum;
        }

        return -1;
    }

}

---

4. 후기