[프로그래머스] 섬 연결하기 (Kruskal)

문제 소개

섬 연결하기 - 프로그래머스 문제를 정리합니다.
이 문제는 n개의 섬을 최소 비용으로 모두 연결하는 최소 신장 트리(MST) 문제입니다.

핵심은 모든 섬이 서로 통행 가능하게 만들되, 총 비용이 최소가 되도록 연결하는 것입니다.

문제 링크: 섬 연결하기 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 전체 통행할 수 있는 다리의 최소 비용을 구해야함 + 각 다리(간선) 비용이 주어짐
   => 최소 신장 트리(MST) / 크루스칼 알고리즘 사용
2. 간선들을 가중치 기준으로 정렬한 뒤, 유니온-파인드로 사이클 방지
3. 간선을 하나씩 선택하며 MST 구성, n-1개의 간선 선택 시 종료

---

해결 과정 및 코드

핵심 아이디어

1. Edge 클래스에 간선 정보를 담고, 비용 기준으로 정렬
2. Union-Find 자료구조로 사이클 여부 판단하며 MST 구성
3. 모든 섬이 하나의 그래프로 연결될 때까지 가장 짧은 간선부터 선택
4. 간선의 수가 n-1개가 되면 MST가 완성되므로 반복 종료

코드

시간 복잡도 : O(E log E)

import java.util.*;

class Solution {
    class Edge implements Comparable<Edge> {
        int start, end, weight;
        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o){
            return Integer.compare(this.weight, o.weight); // 비용 오름차순
        }
    }

    static Edge[] edgeList;
    static int[] parents;

    public int solution(int n, int[][] costs) {
        edgeList = new Edge[costs.length];
        parents = new int[n];

        for (int i = 0; i < costs.length; i++) {
            edgeList[i] = new Edge(costs[i][0], costs[i][1], costs[i][2]);
        }

        makeSet(n);
        Arrays.sort(edgeList); // 비용 기준 정렬

        int result = 0, count = 0;
        for (Edge edge : edgeList) {
            if (!union(edge.start, edge.end)) continue; // 이미 연결된 경우 skip
            result += edge.weight;
            if (++count == n - 1) break; // MST 완성
        }
        return result;
    }

    public void makeSet(int n) {
        for (int i = 0; i < n; i++) parents[i] = i;
    }

    public int find(int a) {
        if (parents[a] == a) return a;
        return parents[a] = find(parents[a]); // 경로 압축
    }

    public boolean union(int a, int b) {
        int aRoot = find(a), bRoot = find(b);
        if (aRoot == bRoot) return false;
        parents[bRoot] = aRoot; // 합집합
        return true;
    }
}