[백준 P14950] 정복자 Java

P14950 정복자 Java

14950번: 정복자

 

문제

서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재한다. 각각 도시는 1번부터 N번까지 번호가 붙여져 있다. 그 중에서 1번 도시의 군주 박건은 모든 도시를 정복하고 싶어한다.

처음 점거하고 있는 도시는 1번 도시 뿐이다. 만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 있어야 한다. 조건을 만족하는 도시 중에서 하나인 A를 선택하면, B를 정복하는 과정에서 A와 B를 연결하는 도로의 비용이 소모된다. 박건은 한번에 하나의 도시만 정복을 시도하고 언제나 성공한다. 한 번 도시가 정복되면, 모든 도시는 경계를 하게 되기 때문에 모든 도로의 비용이 t만큼 증가하게 된다. 한 번 정복한 도시는 다시 정복하지 않는다.

이때 박건이 모든 도시를 정복하는데 사용되는 최소 비용을 구하시오.

 

입력값

첫째 줄에 도시의 개수 N과 도로의 개수 M과 한번 정복할 때마다 증가하는 도로의 비용 t가 주어진다. N은 10000보다 작거나 같은 자연수이고, M은 30000보다 작거나 같은 자연수이다. t는 10이하의 자연수이다.

M개의 줄에는 도로를 나타내는 세 자연수 A, B, C가 주어진다. A와 B사이에 비용이 C인 도로가 있다는 뜻이다. A와 B는 N이하의 서로 다른 자연수이다. C는 10000 이하의 자연수이다.

4 5 8
1 2 3
1 3 2
2 3 2
2 4 4
3 4 1

 

출력값

모든 도시를 정복하는데 사용되는 최소 비용을 출력하시오.

29

 

알고리즘

모든 도시를 최소의 비용만 사용하여 정복해야 한다는 점에서 이 문제는 MST(최소 신장 트리)를 구하는 문제로 이해할 수 있다. 다만 이 문제에는 두 가지 특징이 있다.

 

1. 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 있어야 한다.
2. 한 번 도시가 정복되면 모든 도시는 경계를 하게 되기 때문에 모든 도로의 비용이 t만큼 증가하게 된다.

사실 해당 문제는 가중치 결과만 출력하면 되기 때문에 크루스칼이나 프림 중 어떠한 알고리즘을 사용해도 답은 얻을 수 있다. 하지만 문제의 의미를 파악했을 때 크루스칼 보다는 프림 알고리즘을 사용하는 것이 취지에 맞아보인다. 크루스칼 알고리즘은 간선을 기준으로 MST를 만들기 때문이다. 따라서 크루스칼 알고리즘을 통해서 MST를 구한다면 위의 1번 조건을 항상 만족한다고 보장할 수 없다. 아래의 그림을 보자.

 

 

크루스칼의 경우를 보자. 전체 간선 중 짧은 간선들을 먼저 선택하기 때문에 1, 4번 간선이 선택된 상황에서, 선택될 수 없는 2, 3번 간선이 다음으로 선택된다. 그렇기 때문에 프림 알고리즘을 사용했다. 프림 알고리즘은 우선순위 큐와 인접 리스트 방식을 사용해서 탐색하는 노드와 연결된 모든 노드의 가중치를 계산해서 우선순위 큐에 넣은 뒤, 매 라운드마다 선택할 수 있는 간선 중 가장 작은 간선을 선택하며 MST를 만든다. 이미 방문처리 된 노드와 연결된 간선만 우선순위 큐에 담기기 때문에 1번 특징을 만족할 수 있다. 그림에서 처럼 1, 4번 간선이 연결된 이후에 1번과 4번 노드와 연결된 간선들 중 가장 짧은 1, 2번 간선이 선택되기 때문이다.

 

다음으로 2번 특징으로 인해서 매 라운드마다 가중치가 붙게 된다. 이는 time이라는 변수를 추가해서 해결했다. 가중치를 더하는 과정에서 t와 time을 적절하게 계산하여 결과에 차례대로 더해준다. 이를 통해서 최종 값을 얻을 수 있다.

 

아래는 전체 코드이다.

 

코드

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

public class Main {
    static int N, M, t;
    static long total;
    static boolean[] visited;
    static List<int[]>[] graph;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        visited = new boolean[N + 1];
        graph = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

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

            graph[from].add(new int[] {to, weight});
            graph[to].add(new int[] {from, weight});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return Integer.compare(a[1], b[1]);
        });
        pq.add(new int[] {1, 0});
        int time = -1;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentNode = current[0];
            int currentWeight = current[1];

            if (visited[currentNode]) continue;
            visited[currentNode] = true;

            //맨 처음에는 추가 안하고 넘어가기
            if (time == -1) time++;
            else total += currentWeight + time++ * t;

            for (int[] next: graph[currentNode]) {
                int nextNode = next[0];
                int nextWeight = next[1];

                pq.add(new int[] {nextNode, nextWeight});
            }
        }
        System.out.println(total);
    }
}