자바(백준) 10423 전기가 부족해

오답 노트 & 새로 알게 된 점

MST 응용 문제인 것 같다.

 

항상 부모 배열을 -1로 초기화하고 부모는 하나 뿐인 MST 문제로 무지성으로 풀었는데,

해당 문제를 이렇게 풀면 바로 틀리게 된다.

여기서는 부모 배열 초기화부터 다르게 한다.

 

문제에서 발전소가 여러 개 있고, 발전소끼리 연결할 필요가 없다.

따라서 발전소를 각각 부모라고 생각하면 된다.

부모 배열을 모두 0으로 초기화 한 다음에, 발전소 위치 idx에 부모를 나타내기 위해 -1을 넣는다.

 

그렇다면 당연히 find와 union 메서드가 달라져야한다.

뜻이 달라진 것은 아니지만 안의 기능이 바뀌어야 한다.

 

find 메서드는 부모가 같은지 찾는 메서드로

• parent[v]
  • 음수일 경우
    • 발전소와 연결됐으므로 -1 반환
  • 0
    • 아무것도 연결되지 않음. 즉, 자기 자신을 가르키고 있음
  • 양수
    • 다른 것과 연결되어 있지만 아직 발전소와 연결되지 않음
• union(u, v) : 아래의 조건은 u와 v가 같지 않다는 조건 아래있음
  • u == -1
    • u의 부모가 발전소 이므로 v의 부모를 u의 부모로 바꿔줘야함
  • v == -1
    • 위와 같은 경우
  • u != - 1 && v != -1
    • 연결 시켜줌

 

그래서 check라는 메서드를 통해 parent 배열 중에 발전소와 연결되있지 않은 부분이 있다면

false를 반환하여 계속해서 연결시켜주고,

 

모두 -1로 연결되어있다면 true을 반환하여 끝낸다.

 

---

코드

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

public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M, K;
    static int parent[];
    static ArrayList<Info> al = new ArrayList<Info>();
    static int ans;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }

    static void pro() {
        Collections.sort(al, (o1, o2)->{
            return o1.wei - o2.wei;
        });

        for (int i = 0; i < al.size(); i++) {
            Info info = al.get(i);
            if (find(info.st) != find(info.ed)) {
                union(info.st, info.ed);
                ans += info.wei;

                if(check()) break;
            }
        }

       /* for (int i = 1; i <= N; i++) {
            System.out.println(parent[i]);
        }*/
        System.out.println(ans);
    }

    static boolean check() {
        for (int i = 1; i <= N; i++) {
            if(parent[i] >= 0) {
                return false;
            }
        }

        return true;
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
        K = atoi(st.nextToken());

        parent = new int[N + 1];

        Arrays.fill(parent, 0);

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < K; i++) {
            int num = atoi(st.nextToken());
            parent[num] = -1;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = atoi(st.nextToken());
            int to = atoi(st.nextToken());
            int wei = atoi(st.nextToken());

            al.add(new Info(from, to, wei));
        }
    }

    static int find(int v) {
        if(parent[v] < 0) return -1;
        if(parent[v] == 0) return v;

        parent[v] = find(parent[v]);

        return parent[v];
    }

    static void union(int u, int v) {
        u = find(u);
        v = find(v);

        if(u == v) return;

        if(u == -1){
            parent[v] = -1;
        }
        else if(v == -1){
            parent[u] = -1;
        }
        else{
            parent[v] = u;
        }
    }

    static class Info{
        int st, ed, wei;

        public Info(int st, int ed, int wei) {
            this.st = st;
            this.ed = ed;
            this.wei = wei;
        }
    }
}