[BOJ/] 백준 1197 - 최소 스패닝 트리 (Java)

1197 - 최소 스패닝 트리

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

문제

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

입력
첫째 줄: 정점의 개수 V (1 <= V <= 10,000), 간선의 개수 E (1 <= E <= 100,000)
다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C
A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미
C는 음수일 수도 있으며, 절대값이 1,000,000을 넘지 않음
그래프의 정점은 1~V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있음
(-2,147,483,648 <= 가중치 <= 2,147,483,647)
출력
최소 스패닝 트리의 가중치 

---

풀이

MST (Minimum Spanning Tree): 최소 스패닝 트리

모든 정점을 연결하면서, 사이클 없이 간선 가중치 합이 최소인 그래프

• Kruskal(크루스칼)
  • 간선을 기준으로 가중치가 작은 것부터 선택, 사이클이 생기지 않도록 연결
    • 모든 간선 -> 가중치 기준으로 정렬
    • 사이클 X -> 해당 간선 선택
    • Union-Find로 사이클 여부 판별
  • Union-Find
  • 시간복잡도: $O(E log E)$
• Prim(프림)
  • 정점을 기준으로, 연결 가능한 가장 짧은 간선 매번 선택해 확장
    • 정점 하나에서 시작
    • 현재 MST에서 연결 가능한 간선들 중 가장 짧은 것 선택
    • 새 정점 MST 포함
    • 모든 정점 포함될 때까지 반복
  • PriorityQueue
  • 시간복잡도: $O(E log V)$

 

<Union-Find>

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

static void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a;
}

 

사이클 X -> 연결 

 

for (Node node : arr) {
    if (find(node.from) != find(node.to)) {
        union(node.from, node.to);
        total += node.weight;
    }
}

---

예시

정점 수: 3, 간선 수: 3, 간선 정보: 1 2 1 / 2 3 2 / 1 3 3

-> 오름차순 정렬: 1 2 1 / 2 3 2 / 1 3 3

• `parent = [0, 1, 2, 3]` // 0 사용 X
  • `find(1) = 1` != `find(2)=2` -> 서로 다른 집합 => 연결
  • `union(1, 2)` -> `parent[2] = 1`
  • => (1-2) 간선 선택, 비용: 1
• `parent = [0, 1, 1, 3]`
  • `find(2) = 1` != `find(3) = 3` -> 서로 다른 집합 => 연결
  • `union(2, 3)` -> `parent[3] =  1`
  • => (2-3) 간선 선택, 비용: 2
• `parent = [0, 1, 1, 1]`
  • `find(1) = 1` == `find(3) = 1` -> 같은 집합 => 연결 X

=> 총 비용: 1 + 2 = 3

---

코드

크루스칼 알고리즘

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

// 최소 스패닝 트리
class Edge implements Comparable<Edge> {
    int from, to, weight;

    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    public int compareTo(Edge o) {
        return weight - o.weight;
    }
}

public class boj_1197 {
    static int[] parent;

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

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) parent[b] = a;
    }

    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());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            edges.add(new Edge(A, B, C));
        }

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

        Collections.sort(edges);

        int total = 0;
        for (Edge edge : edges) {
            if (find(edge.from) != find(edge.to)) {
                union(edge.from, edge.to);
                total += edge.weight;
            }
        }

        System.out.println(total);
    }
}