© 2025 anveloper.dev
GitHub·LinkedIn·Contact

목차

  • 문제
  • 입력
  • 출력
  • 예제
  • 풀이
  • 코드
  • 복잡도
풀이 목록으로 돌아가기

BOJ 10423 - 전기가 부족해

2022-12-30
BOJ
골드 III
java
원본 문제 보기
그래프 이론
최소 스패닝 트리

문제

BOJ 10423 - 전기가 부족해

N개의 도시와 M개의 케이블이 있다. K개의 도시에는 발전소가 있다. 모든 도시에 전기를 공급하기 위해 케이블을 설치할 때, 케이블 설치 비용의 합을 최소화하는 프로그램을 작성하시오. 발전소가 있는 도시끼리는 연결할 필요가 없다.

입력

첫째 줄에 N, M, K가 주어진다. 둘째 줄에 발전소가 있는 K개의 도시 번호가 주어진다. 이후 M개의 줄에 케이블 정보 u, v, w가 주어진다.

  • 1 ≤ N ≤ 1,000
  • 1 ≤ M ≤ 100,000
  • 1 ≤ K ≤ N

출력

케이블 설치 비용의 최솟값을 출력한다.

예제

입력:

9 12 3
1 3 9
1 2 3
1 4 4
2 3 1
2 5 2
3 6 7
4 5 8
4 7 5
5 6 9
5 8 6
6 9 11
7 8 10
8 9 12

출력:

31

풀이

핵심 아이디어: 발전소가 있는 K개의 도시를 모두 하나의 가상 노드로 묶어서 크루스칼 알고리즘을 적용한다. 발전소끼리는 이미 연결되어 있으므로, Union-Find에서 발전소 노드의 부모를 -1(특별 표시)로 초기화하고 서로 같은 집합으로 취급한다.

  1. 초기화: 발전소 노드들의 부모를 -1로 설정하여 하나의 집합으로 묶는다.
  2. 간선 정렬: 모든 케이블을 비용 기준 오름차순으로 정렬한다.
  3. 크루스칼 실행: 비용이 작은 간선부터 연결을 시도한다. 두 노드가 같은 집합이면 건너뛰고, 다르면 합친다. 이때 한쪽이 발전소 집합(-1)이면 다른 쪽을 -1에 합류시킨다.
  4. 조기 종료: 모든 노드의 부모가 -1이면 전기 공급이 완료된 것이므로 탐색을 중단한다.

코드

package day349;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
// import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Day326BOJ10423전기가부족해 {
    static int N, M, K, ans = 0;
    static int[] arr;
    static List<int[]> edges;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        arr = new int[K];
        edges = new ArrayList<>();
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            edges.add(new int[] { u, v, w });
        }
 
        edges.sort((e1, e2) -> e1[2] - e2[2]);
 
        kruscal();
        System.out.println(ans);
        br.close();
    }
 
    // kruscal
    static int[] p;
 
    private static void kruscal() {
        p = new int[N + 1];
        init();
 
        for (int i = 0; i < K; i++) {
            p[arr[i]] = -1;
        }
 
        for (int i = 0; i < M; i++) {
            int[] tmp = edges.get(i);
            if (unionSet(tmp[0], tmp[1])) {
                ans += tmp[2];
                if (check()) {
                    break;
                }
            }
            // System.out.println(Arrays.toString(parent));
        }
    }
 
    private static boolean check() {
        for (int i = 1; i < N + 1; i++) {
            if (p[i] != -1)
                return false;
        }
        return true;
    }
 
    private static void init() {
        for (int i = 1; i < N + 1; i++) {
            p[i] = i;
        }
    }
 
    private static boolean unionSet(int a, int b) {
        a = findSet(a);
        b = findSet(b);
        if (a == b)
            return false;
        if (b == -1)
            p[a] = b;
        else
            p[b] = a;
        return true;
    }
 
    private static int findSet(int a) {
        if (p[a] == -1)
            return -1;
        return p[a] = (a == p[a]) ? a : findSet(p[a]);
    }
}

복잡도

  • 시간: O(E log E) — 간선 정렬이 지배적 (크루스칼 알고리즘)
  • 공간: O(V + E) — Union-Find 배열 및 간선 리스트