(백준) 일감호에 다리 놓기 _ 17490

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

 

🐢 설명

원형의 호수를 둘러싼 건물들에 대해 최소 스패닝 트리를 만들어야 한다.

이때 중요한 점은 건물군(동일한 부모를 갖는 건물들)이 하나라면, 즉 건물 사이를 막는 공사가 없거나 하나라면, 아무리 다리를 만드는 비용이 비싸도 모든 다리를 만들 필요없이 모든건물들을 갈 수 있으므로 무조건 YES 이다.

 

위 예외 사항을 제외하면 일반적인 유니온 파인드로 문제를 풀 수 있다.

1. 각 건물들의 부모를 자신의 번호로 지정하고, 건물 사이의 공사 여부를 체크해준다.

2. 각 건물들을 돌면서 같은 건물군인지 확인하고 & 사이에 공사구간이 없다면 같은 건물군으로 묶어준다. 이때 마지막 건물은 첫번째 건물까지 확인하게 해준다.

3. 건물번호와 부모 건물 번호가 같을 때만 비용을 누적해서 더하고 & 이 때의 경우를 카운트한다.

4. 만약 건물번호와 부모 건물이 같은 경우가 한번 이하라면 돌다리는 필요 없으므로 YES를 출력한다.

5. 그외의 경우에는 총 돌의 개수보다 필요한 돌의 개수가 적거나 같을 때만 YES, 나머지는 NO를 출력한다.

 

🐢코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 일감호에다리놓기_17490 {
    static int N, M;
    static long K;
    static int[] parent;
    static int[] stoneCost;
    static boolean[] isBlocked;

    public static void main(String[] args) throws IOException {
        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 = Long.parseLong(st.nextToken());
        parent = new int[N + 1];
        stoneCost = new int[N + 1];
        isBlocked = new boolean[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            parent[i] = i;
            stoneCost[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            isBlocked[end] = true;
        }

        makeUnion();
        makeBridge();
    }

    private static void makeUnion() {
        for (int u = 1; u <= N; u++) {
            int v = (u + 1) % (N + 1);
            if (v == 0) v = 1;
            if (find(u) != find(v)) {
                if (isBlocked[v]) continue; // 공사 체크
                union(u, v);
            }
        }
    }

    private static int find(int node) {
        if (parent[node] == node) return node;
        return parent[node] = find(parent[node]);
    }

    private static void union(int u, int v) {
        u = find(u);
        v = find(v);
        if (stoneCost[u] <= stoneCost[v]) { // 건물군을 묶을 때 비용이 가장 적은 건물을 부모로 함
            parent[v] = parent[parent[u]];
        } else parent[u] = parent[parent[v]];
    }

    private static void makeBridge() {
        long needCost = 0;
        int parentCount = 0;

        for (int i = 1; i <= N; i++) {
            if (find(i) == i) { // 건물 군에서 가장 적은 비용을 더함
                needCost += stoneCost[i];
                parentCount++;
            }
        }
        if (needCost <= K || parentCount <= 1) { // 부모가 하나 이하이거나 or 비용을 댈 수 있으면 YES
            System.out.println("YES");
        } else System.out.println("NO");
    }
}

🐢 마무리