[백준, BOJ 14950] 정복자 (java)

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

메모리: 26,704 KB , 시간: 376 ms

사용 알고리즘: 그래프 이론, 최소 스패닝 트리

728x90

---

처음에 다익스트라로 풀었다가, 알고리즘 분류를 보고 크루스칼 알고리즘으로도 풀 수 있겠다고 알게 돼서 다시 크루스칼로 풀었다...

알고리즘 며칠 안 했다고 이전에는 당연히 크루스칼로 풀었을 문제를 다익스트라로 풀었네,,

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int[] parent;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        // 크루스칼 알고리즘
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);

        int A, B, C;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            pq.add(new int[] {A, B, C});
        }

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

        int[] now;
        int result = 0;
        int count = 0;
        while(!pq.isEmpty()) {
            now = pq.poll();

            if(union(now[0], now[1])) { // 아직 정복하지 않은 도시를 발견했을 경우
                result += now[2] + (t * count++); // 비용 더하기
            }
        }

        System.out.println(result);
    }

    private static int find(int a) {

        if(parent[a] == a) return a;

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

    private static boolean union(int a, int b) {

        a = find(a);
        b = find(b);

        // 이미 연결되어 있다면 false
        if(a == b) return false;

        // 아직 연결 전이라면 true;
        if(a < b) parent[b] = a;
        else parent[a] = b;
        return true;
    }
}