[백준] 10423번. 전기가 부족해(JAVA)

문제

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

---

풀이(29분)

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

class Main {
    static int[] parent;
    static boolean[] hasPower;
    static int n, m, k, nonLinked, cost;
    static List<Node> edges = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        nonLinked = n;

        parent = new int[n];
        hasPower = new boolean[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int powerCity = Integer.parseInt(st.nextToken()) - 1;
            hasPower[powerCity] = true;
            nonLinked--;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()) - 1;
            int v = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken());
            edges.add(new Node(u, v, c));
        }

        Collections.sort(edges);

        for (Node edge : edges) {
            int u = find(edge.start);
            int v = find(edge.end);

            if (u == v) continue;

            boolean uHasPower = hasPower[u];
            boolean vHasPower = hasPower[v];

            // 전기가 통하지 않는 도시가 전기가 통하는 그룹과 연결될 때만 감소
            if ((uHasPower && !vHasPower) || (!uHasPower && vHasPower)) {
                cost += edge.cost;
                union(u, v);
                nonLinked--;
            } else if (!uHasPower && !vHasPower) {
                // 둘 다 전기 없을 때도 일단 union
                cost += edge.cost;
                union(u, v);
            }

            if (nonLinked == 0) break;
        }

        System.out.println(cost);
    }

    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        parent[rootY] = rootX;
        hasPower[rootX] = hasPower[rootX] || hasPower[rootY]; // 전기 연결 여부 합치기
    }

    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    static class Node implements Comparable<Node> {
        int start, end, cost;

        public Node(int s, int e, int c) {
            start = s;
            end = e;
            cost = c;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
}

---

문제 풀이 전략

 

먼저 MST를 사용하여 사이클이 없는 묶음들을 구한다.

다만, 이때 이미 발전소에 연결되어 있다면 더 이상 탐색을 진행하지 않는다.

 

최종적으로 모든 도시들이 발전소에 연결되어있다면 종료를 한다.

 

MST의 대표적인 알고리즘인 크루스칼 알고리즘을 모른다면 참고하자.

[도구정리] 최소 신장 트리(MST) - 크루스칼(kruskal) 알고리즘