[BOJ/백준] 1197 - 최소 스패닝 트리(Java)(최소신장트리 알고리즘)

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

🌲 최소신장트리(MST, Minimum Spanning Tree)

📌 최소신장트리란?

• 정의: 주어진 무방향 가중치 그래프에서 모든 정점을 연결하면서, 간선의 가중치 합이 최소인 트리
• 조건
  • 모든 정점이 연결되어 있어야 함
  • 사이클이 없어야 함 → 트리
  • 간선의 가중치 합이 최소

---

✅ 활용 예시

• 네트워크 설계 (통신망, 전력망)
• 클러스터링
• 회로 설계

---

💡 MST 알고리즘 2가지

1. Kruskal’s Algorithm (크루스칼 알고리즘)

• 동작 방식: 간선을 가중치 기준으로 오름차순 정렬 후, 사이클이 생기지 않도록 간선을 하나씩 선택
• 핵심 자료구조: Union-Find (Disjoint Set)

✏️ 알고리즘 단계

1. 간선들을 가중치 기준으로 정렬
2. 가중치가 작은 간선부터 하나씩 선택
3. 사이클이 생기지 않으면 MST에 포함
4. MST에 (정점 수 - 1)개의 간선이 생기면 종료

⏱ 시간복잡도

• O(E log E) (간선 정렬이 가장 오래 걸림)

---

2. Prim’s Algorithm (프림 알고리즘)

• 동작 방식: 하나의 정점에서 시작해, 연결된 간선 중 가중치가 가장 작은 간선을 선택하며 MST 확장
• 핵심 자료구조: Priority Queue (우선순위 큐)

✏️ 알고리즘 단계

1. 임의의 시작 정점을 선택
2. 연결된 간선 중 가장 가중치가 작은 간선을 선택
3. 해당 간선으로 연결된 정점이 MST에 없다면 포함
4. 모든 정점이 MST에 포함될 때까지 반복

⏱ 시간복잡도

• 인접 리스트 + 힙 사용 시: O(E log V)

---

🔄 두 알고리즘 비교

항목 Kruskal 알고리즘 Prim 알고리즘

방식	간선 중심	정점 중심
자료구조	Union-Find	Priority Queue
그래프 형태	간선이 적은 경우 유리	간선이 많은 경우 유리
시간복잡도	O(E log E)	O(E log V) (Heap 사용 시)

---

🧠 MST 관련 개념

• 사이클: MST는 사이클을 포함하지 않음
• 유일성: 간선 가중치가 모두 다르면 MST는 유일함
• 연결 그래프: MST는 모든 정점이 연결된 그래프에서만 정의됨

---

크루스칼 알고리즘을 사용한 풀이

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

class Edge {
    int start;
    int end;
    int cost;

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

    @Override
    public String toString() {
        return this.start + " " + this.end + " " + this.cost;
    }
}


public class Main {
    static int V, E;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        File file = new File("input.txt");
        BufferedReader br = file.exists()
                ? new BufferedReader(new FileReader(file))
                : new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        parent = new int[V + 1];
        for (int i = 1; i < V + 1; i++) {
            parent[i] = i;
        }
        List<Edge> edgeList = new ArrayList<>();
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            edgeList.add(new Edge(start, end, cost));

        }
        edgeList.sort((a, b) -> a.cost - b.cost);

        int cnt = 0;
        int sumCost = 0;
        for (Edge e : edgeList) {
            if (find(e.start) != find(e.end)) {
                union(e.start, e.end);
                sumCost = sumCost + e.cost;
                cnt = cnt + 1;
                if (cnt == V - 1) break;
            }

        }
        System.out.println(sumCost);
    }

    static int find(int x) {
//        System.out.println(parent[x] + " " + x);
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
//        System.out.println("union : "+a + b + rootA+" "+ rootB);
        if (rootA != rootB) {
            parent[rootB] = rootA;
        }
    }

}