[SWEA] 3124: 최소 스패닝 트리(Java)

💡 문제

SW Expert Academy

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력으로 주어지는 그래프는 하나의 연결 그래프임이 보장된다.

입력

가장 첫 번째 줄에는 전체 test case의 수 T(1≤T≤10)가 주어진다.

각 케이스의 첫째 줄에는 정점의 개수 V(1≤V≤100,000)와 간선의 개수 E(1≤E≤200,000)가 주어진다.

다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다.

C는 음수일 수도 있으며, 절대값이 1,000,000을 넘지 않는다.

출력

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(테스트케이스 번호) “를 출력하고, 최소 스패닝 트리의 가중치를 출력한다.

힌트

최소 스패닝 트리를 계산하는 알고리즘으로 Prim's algorithm과 Kruskal's algorithm이 있다.

본 문제에서는 주어지는 정점과 간선의 개수가 많기 때문에 효율적인 알고리즘 구현이 필요하다.

Prim's algorithm을 이용할 경우, 자료구조 힙(heap)을 이용해야 한다.

Kruskal's algorithm을 이용할 경우, Disjoint Set(서로소 집합) 혹은 Union-Find 알고리즘을 이용해야 한다.

예제 입력 1

1
3 3
1 2 1
2 3 2
1 3 3

예제 출력 1

#1 3

---

💡 접근 방법

S가 0일때는 sum=0의 초기화와 겹치므로 신경써줘야한다

부분집합으로 풀면 쉽게 풀 수 있음

---

🤦‍♀️ My Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_3124 {
    static class Edge implements Comparable<Edge> {
        int start;
        int end;
        int weight;

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

        @Override
        public int compareTo(Edge o) { // 가중치 오름차순으로 저장
            return this.weight - o.weight;
        }

    }

    static Edge[] edgeList;
    static int[] parents;
    static int V, E;

    public static void make() { //유일한 멤버를 포함하는 새로운 집합을 생성 
        for (int i = 0; i < V; i++) {
            parents[i] = i;
        }
    }

    public static int find(int a) { 집합 찾는 연산 
        if (parents[a] == a) {
            return a;
        }
        return parents[a] = find(parents[a]);
    }

    public static boolean union(int a, int b) {  //두 집합을 합치는 연산 
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot) {
            return false;
        }

        parents[bRoot] = aRoot;
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            parents = new int[V];
            edgeList = new Edge[E];

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

                edgeList[k] = new Edge(from, to, weight);

            } // 간선 저장

            make();

            // 간선비용이 작은 순서대로 정렬
            Arrays.sort(edgeList);
            long result = 0;
            int count = 0;// 연결 간선수
            for (Edge edge : edgeList) {
                if (union(edge.start - 1, edge.end - 1)) { // 싸이클이 발생하지 않았으면
                    result += edge.weight; // 가중치값 저장 
                    if (++count == V - 1) { // 연결 간선수가 정점수 -1이면 다 연결함 
                        break;
                    }
                }
            }
            System.out.println("#" + i + " " + result);
        }
    }
}

---