[백준 1197] 최소 스패닝 트리 / 자바 / 자료구조(크루스칼 알고리즘/유니온 파인드)

#문제         

레벨: G4
알고리즘: 자료구조(최소 스패닝 트리)
풀이시간: 
힌트 참조 유무:

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

---

#문제 풀이        

MST란 n개의 정점을 최소한의 간선(n-1)으로 이은 트리(싸이클x)이다. MST는 크루스칼 알고리즘과, 프릴 알고리즘을 사용해 풀 수 있다. 

크루스칼 알고리즘은 유니온 파인드 자료구조를 사용한다.  프림 알고리즘은 다익스트라 비슷하게 풀이한다. 

크루스칼 vs 프림

	크루스칼 알고리즘	프림 알고리즘
탐색 방법	간선 위주	정점 위주
탐색 과정	시작점 따로 지정없이 최소 비용의 간선을 차례대로 대입하면서 사이클이 이루어지기 전까지 탐색	시작점을 지정한 후 가까운 정점을 선택하면서 모든 정점을 탐색
사용	간선의 개수가 적은 경우 크루스칼 알고리즘이 용이	간선의 개수가 많은 경우에는 정점 위주 탐색인 프림이 용이
시간복잡도	O(ElogV)	O(ElogV)

 

크루스칼 알고리즘 

1. 간선 데이터를 오름차순 정렬
2. 간선을 확인하며 현 간선이 사이클을 발생시키는지 확인
   • 발생시키지 않으면 MST에 포함
3. 모든 간선에 대해 반복한다

 

프림 알고리즘

  1. 무작위 간선을 선택한다.

  2. To노드에서 최소한의 비용으로 갈 수 있는 노드를 선택한다.

          - 방문하지 않았으면 MST에 포함

  3. 모든 노드를 방문할 때까지 2를 반복한다.

---

#풀이 코드      

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

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

class DisjointSet {
    int[] parent, rank;

    public DisjointSet(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);

        if (rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;
        } else if (rank[xRoot] > rank[yRoot]) {
            parent[yRoot] = xRoot;
        } else {
            parent[yRoot] = xRoot;
            rank[xRoot]++;
        }
    }
}

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

        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        List<Edge> edges = new ArrayList<>();

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken()) - 1;
            int B = Integer.parseInt(st.nextToken()) - 1;
            int C = Integer.parseInt(st.nextToken());
            edges.add(new Edge(A, B, C));
        }

        Collections.sort(edges);

        DisjointSet ds = new DisjointSet(V);
        long totalWeight = 0;
        int edgesAdded = 0;

        for (Edge edge : edges) {
            if (ds.find(edge.src) != ds.find(edge.dest)) {
                ds.union(edge.src, edge.dest);
                totalWeight += edge.weight;
                edgesAdded++;
                if (edgesAdded == V - 1) break;
            }
        }

        System.out.println(totalWeight);
    }
}