[SWEA] 4006. 고속도로 건설 2

[SWEA] 4006. 고속도로 건설 2

Problem

제출일 : 2019-12-16

문제 풀이 시간 : 25M

난이도 : ★★

---

link : https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxyoNqAiQDFAW4

그러나 비싼 비용의 문제에 부딪혀, 정부는 최소 비용으로 모든 도시 간을 이동할 수 있게 하고 싶어한다.

또한 하나의 제약이 더 있는데, 언덕 등을 깎지 않는 친환경 건설을 위해 어떤 도시끼리는 직접 도로를 이을 수 없다.

친환경 건설을 위해 이을 수 있는 도로의 목록이 주어질 때, 정부를 도와 모든 도시 간을 잇는 고속도로를 건설하는 최소 비용을 알아내자.

input

첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 8)

각 테스트 케이스의 첫 번째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 50,000)

각 테스트 케이스의 두 번째 줄에 도로 후보의 수 M이 주어진다. (1 ≤ M ≤ 200,000)

각 테스트 케이스의 세 번째 줄부터 M개의 줄에 걸쳐 각 도로 후보의 정보 s, e, c가 주어진다.

s와 e는 도로 후보가 잇는 각 도시의 번호이고, c는 그 도로를 건설하는데 드는 비용이다. (1 ≤ c ≤ 10,000)

항상 모든 도시를 잇는 고속도로를 건설할 수 있는 입력만 주어진다.

Output

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, 모든 도시를 잇는 고속도로를 건설하는데 드는 최소 비용을 출력한다.

Example

input

1
5
8
1 2 4
1 3 9
1 4 21
2 3 8
2 4 17
3 4 16
5 2 20
5 4 30

output

#1 48

Solution & Inpression

크루스칼 알고리즘을 이용하여 구현하였다.

시간 복잡도를 줄이기 위해 PriorityQueue를 이용하여 가장 적은 비용의 간선을 추출하고 Union-Find알고리즘을 이용 싸이클을 검사했다.

MST 알고리즘은 예전에 확실히 개념을 공부하고 기억하고 있어 쉽게 구현이 가능했다.

Code

언어 : JAVA

import java.io.FileInputStream;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {
    final static int MAX = 50009;
    static PriorityQueue<Edge> pq;
    static int parents[] = new int[MAX];
    static int N, M, ans;

    static class Edge implements Comparable<Edge> {
        int start, end, cost;

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost > o.cost ? 1 : -1;
        }

    }

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            M = sc.nextInt();
            pq = new PriorityQueue<>();
            for (int i = 1; i <= M; i++) {
                pq.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()));
            }

            ans = 0;
            makeSet();

            while (!pq.isEmpty()) {
                Edge e = pq.poll();
                int x = find(e.start);
                int y = find(e.end);
                if (x == y)
                    continue;
                else {
                    ans += e.cost;
                    union(x, y);
                }
            } // end of while
            System.out.println("#" + tc + " " + ans);
        }
    }// end of main

    private static void union(int x, int y) {
        if (x > y)
            parents[x] = parents[y];
        else
            parents[y] = parents[x];
    }

    private static int find(int x) {
        if (x == parents[x])
            return parents[x];
        else
            return x = find(parents[x]);
    }

    private static void makeSet() {
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
        }
    }

}