[BOJ] 23743 - 방탈출

문제

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

링크를 확인해보세요.

www.acmicpc.net

문제 정리

시간 제한	메모리 제한	정답 비율
2 초	1024 MB	48.5%

요약

• N 개의 방이 있고, 각 방에는 사람 한 명씩 존재합니다.
• 목표는 모든 방에서 출구로 탈출할 수 있게 만드는 것입니다.
• 이때 두 방을 연결하는 워프를 설치할 수 있습니다.
  • 워프는 최대 M 개 설치 가능하고, 각 워프는 설치 비용이 존재합니다.
• 각 방에 직접 출구로 나가는 비상탈출구를 설치할 수 있습니다.
  • 이것도 방마다 설치 비용이 존재합니다.
• 모든 사람이 출구로 탈출할 수 있게 워프와 출구를 설치하는 데 필요한 최소 시간을 구해야 합니다.

입력 조건

• 첫 줄에 N과 M이 주어집니다.
  • N (방의 개수) : 2 ~ 200,000
  • M (워프 개수) : 1 ~ 100,000
• 다음 M개 줄에는 워프 정보 나타내는 세 정수(a, b, c)가 주어집니다.
  • a방과 b방 사이를 잇는 워프를 설치하는데 걸리는 시간 c 임을 의미합니다.
  • a, b : 1 ~ N, a != b
  • c : 1 ~ 10,000
  • 같은 두 개의 방을 잇는 워프가 여러 개 존재할 수 있습니다.
• 마지막 줄에는 N개의 정수 t1, …, tn이 주어집니다.
  • ti는 i번째 방에 비상탈출구를 설치하는 데 드는 비용을 의미합니다.
  • t : 1 ~ 10,000

출력

• 모든 친구가 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하는 데 걸리는 최소 시간을 출력해야 합니다.

---

문제 풀이

문제를 정보를 직관적으로 해석하기 위하여 다음과 같은 규칙으로 그래프를 그려 보겠습니다.

변환 규칙

• 방 : 하나의 정점
• 워프 : 두 방을 연결하는 간선
• 출구 : 하나의 정점
• 비상 탈출구 : 방과 출구를 연결하는 간선

예제

3 1
1 2 2
3 3 3

그래프 모습

여기서 저희의 목표인 “모든 방에서 출구로 탈출”을 그래프 입장에서 해석하면 다음과 같습니다.

• 모든 정점이 하나로 연결되어야 합니다.
• 사이클이 없어야 합니다. (불필요한 비용 제거)
• 그래프의 모든 간선의 합의 최소여야 합니다.

결론

위 조건을 종합하면 그래프를 구성한 뒤 최소 스패닝 트리(MST)을 구하는 문제로 해석할 수 있습니다.

크루스칼 알고리즘을 사용하여 해결하였습니다.

---

풀이 코드

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


class Main {

    int getParent(int child, int[] parent) {
        if (child == parent[child]) {
            return child;
        }

        parent[child] = getParent(parent[child], parent);
        return parent[child];
    }

    void solve() throws Exception {
        // 변수 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int N = Integer.parseInt(st.nextToken());   // 방의 개수
        int M = Integer.parseInt(st.nextToken());   // 워프의 개수

        List<int[]> edges = new ArrayList<>();

        // 워프 정보를 간선으로 저장.
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            edges.add(new int[] {node1, node2, value});
        }

        // 각 방에서 출구 까지 비용을 간선으로 저장.
        st = new StringTokenizer(br.readLine());

        for (int node = 1; node <= N; node++) {
            int value = Integer.parseInt(st.nextToken());

            edges.add(new int[] {0, node, value});
        }

        // 비용 기반 오름 차순으로 정렬 -> 크루스칼
        edges.sort(Comparator.comparingInt(a -> a[2]));

        // union & find -> 크루스칼.
        int[] parent = new int[N + 1];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }

        int answer = 0;

        for (int[] edge: edges) {
            int node1Parent = getParent(edge[0], parent);
            int node2Parent = getParent(edge[1], parent);

            if (node1Parent != node2Parent) {
                answer += edge[2];

                parent[node2Parent] = node1Parent;
            }
        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solve();
    }
}