백준 14950 (정복자) - java

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

14950번: 정복자

 

문제

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

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

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

 

유형 : MST

 

접근 방식

• 시간이 매초 t씩 증가하기 때문에 조금 헷갈릴 수 있지만 상관없다.
• 결국 완성된 정복 국가의 형태는 MST이다. 
  • 즉 매번 점령된 땅을 기준으로 확장하는 (프림 알고리즘)의 결과나 크루스칼의 결과나 똑같다는 것이다.
  • 그저 간선을 한 개 고를 때마다 t값의 증가만 잘 고려하면 되는 문제이다.
• 예제를 예로 들어 설명하자면 아래 설명에는
  • 2 + (1+8) + (2+8+8)이지만 
  • 이 방식을 크루스칼로 풀 경우 1 + (2+8) + (2+8+8)인데 차이가 없다는 것이다 !

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;

    static int m = 0;

    static int t = 0;

    static int[] root;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        root = new int[n+1];
        for(int i=1;i<=n;i++){
            root[i] = i;
        }

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );


        for(int i=1;i<=m;i++){
            st = new StringTokenizer(bf.readLine(), " ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int v3 = Integer.parseInt(st.nextToken());

            pq.add(new Node(v1,v2,v3));
        }

        int tmp = 0;
        int result = 0;
        int num = 0;

        while(!pq.isEmpty()){

            Node cur = pq.poll();

            if(find(cur.v1) != find(cur.v2)){
                union(cur.v1,cur.v2);

                result += tmp + cur.c;
                tmp += t; // 간선을 한 개 뽑을 때 마다 t초씩 값 증가 (0 -> 8 -> 8+8)
                num += 1; // n-1개의 간선을 뽑을 경우 종료하기 위해서
            }

            if(num == n-1){
                break;
            }
        }

        System.out.println(result);
        bf.close();
    }

    static int find(int x){
        if(x == root[x])
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){

        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;

        else{
            root[x] = y;
        }

    }
}
class Node{
    int v1;
    int v2;
    int c;

    Node(int v1,int v2,int c){
        this.v1 = v1;
        this.v2 = v2;
        this.c = c;
    }
}