백준 1414 - 불우이웃돕기

문제

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

리뷰

크루스칼을 이용해 풀이할 수 있는 문제였다.

문제 조건에 따라 다솜이가 기부할 수 있는 랜선 길이의 최댓값은
아래와 같이 재정의할 수 있다.

기부 가능한 최댓값 = 모든 랜선의 길이 - MST 형성 랜선의 길이

따라서, 크루스칼 알고리즘을 통해 주어진 간선들을 통해 MST를 형성하고 MST를
구성하는 간선들의 비용(=랜선 길이)의 합을 구한뒤, 전체 랜선의 길이와의 차이값을
구하여 답을 도출할 수 있다.

로직의 시간복잡도는 크루스칼의 시간복잡도인 $O(Nlog(N^2))$으로 수렴하고,
이는 $N=50$인 최악의 경우에도 무난히 제한 조건 2초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

import static java.lang.Integer.*;

public class Main {
    static int N;
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.w));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = parseInt(br.readLine());
        parent = new int[N];

        String line;
        char val;
        int w, total = 0;

        for (int u = 0; u < N; u++) {
            line = br.readLine();
            for (int v = 0; v < N; v++) {
                val = line.charAt(v);

                if (val == '0') continue;

                w = Character.isUpperCase(val) ? val - 'A' + 27 : val - 'a' + 1;
                total += w;
                pq.offer(new Edge(u, v, w));
            }
        }

        int result = kruskal();
        System.out.println(result == -1 ? -1 : total - result);
        br.close();
    }

    static int kruskal() {
        Arrays.fill(parent, -1);
        int mstCost = 0;
        int selected = 0;

        while (!pq.isEmpty() && selected < N - 1) {
            Edge e = pq.poll();

            if (!union(e.u, e.v)) continue;

            mstCost += e.w;
            selected++;
        }

        return selected == N - 1 ? mstCost : -1;
    }

    static boolean union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        if (r1 == r2) return false;

        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }

        return true;
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static class Edge {
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과