백준 23743 - 방탈출

문제

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

리뷰

크루스칼을 통해 풀이할 수 있는 간단한 문제였다.

주어진 문제의 조건을 풀어서 살펴보면

• 최소 1개의 방에 탈출구가 설치되어야 하고, 나머지 방이 그와 이어져 있어야 함
• 해당 경로를 가장 적은 비용으로 구성할 수 있어야 함

이렇게 위 두 조건을 충족시켜야 한다.

탈출구가 반드시 하나는 있어야 하는데

• 어느 방에 탈출구를 설치할지
• 탈출구가 이미 설치된 방에 연결하는 것이 이득인지 아니면 현재 방에 탈출구를
  설치하는 것이 이득인지

위 두 여부를 판단하는 것이 이 문제의 풀이를 도출하는 핵심이었던 것 같다.

필자는 아예 탈출구를 상징하는 정점을 인덱스 0으로 parent 배열내에서 설정하고
방 $i$에 탈출구를 설치하는 것을 0과 $i$의 간선으로 표현하여 비용 기준 최소힙에
다른 간선들과 함께 포함시킨 다음 $0$~$N$까지 MST를 형성하는 방식으로 답을
도출하였다.

로직의 시간복잡도는 크루스칼의 $O(Nlog(N+M))$으로 수렴하고 이는 $N=200,000$,
$M=100,000$인 최악의 경우에도 무난히 제한 조건 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 java.util.StringTokenizer;

import static java.lang.Integer.*;

public class Main {
    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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        parent = new int[N + 1];
        int u, v, w;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());
            w = parseInt(st.nextToken());

            pq.offer(new Edge(u, v, w));
        }

        st = new StringTokenizer(br.readLine());
        for (v = 1; v <= N; v++) {
            w = parseInt(st.nextToken());
            pq.offer(new Edge(0, v, w));
        }

        System.out.println(kruskal(N + 1));
        br.close();
    }


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

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

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

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

        return sum;
    }

    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;
        }
    }
}

결과