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

프로그래머스

 

💬 문제 설명

연결되어 있는 두 정점 정보와 가중치 정보가 주어졌을 때 최소 비용(간선의 가중치의 합)으로 모든 섬을 연결하고 해당 최소 비용을 반환하라.

 

📌 주의 사항

• 모든 섬 연결 + 최소 비용 → 최소 신장 트리(MST) 구성

 

👌 문제 풀이

1. 모든 섬을 최소 비용으로 연결해야 하므로 최소 신장 트리 알고리즘을 사용해야 한다.
2. 간선 정보를 알려주고 있으므로 간선 배열로 만들어서 사용하자.
   • 간선 배열이므로 크루스칼 알고리즘을 사용해야겠다!
3. 간선 배열을 가중치로 오름차 순 정렬
4. 모든 간선이 연결될 때까지 union-find 진행
   • 두 간선을 연결했을 때 사이클이 발생하지 않으면 union하고 총 비용에 해당 간선의 가중치를 더해줌

 

💻 코드

import java.util.Arrays;

class Solution {
    
    public int[] parents;
    
    public int solution(int n, int[][] costs) {
    	// 1. 간선 배열 정의
        Edge[] edges = new Edge[costs.length];
        
        for (int i = 0; i < costs.length; i++) {
            int u = costs[i][0];
            int v = costs[i][1];
            int w = costs[i][2];
            
            edges[i] = new Edge(u, v, w);
        }
        
        // 2. union-find를 위한 부모 배열 정의
        parents = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
        
        // 3. 가중치로 오름차순 정렬
        Arrays.sort(edges);

	// 4. 크루스칼로 MST 구성
        int result = 0; // 총 비용
        int count = 0; // 연결 간선 수
        for (Edge edge: edges) {
            if (union(edge.u, edge.v)) { // 싸이클이 발생하지 않았으면 (같은 집합에 없다면)
                result += edge.w;

                if (++count == n - 1) { // 연결 간선 수가 (정점 수 - 1) 이면 다 연결한 것임
                    break;
                }
            }
        }
 
        return result;
    }
    
    int find(int u) {
        if (parents[u] == u) {
            return u;
        }
        
        return parents[u] = find(parents[u]);
    }
    
    boolean union(int u, int v) {
        u = find(u);
        v = find(v);
        
        if (u == v) {
            return false;
        }
        
        if (u < v) {
            parents[v] = u;
        } else {
            parents[u] = v;
        }
        
        return true;
    }
}

// 간선 정보를 담을 클래스
class Edge implements Comparable<Edge> {
    
    int u, v, w;
    
    Edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
    
    // 가중치로 오름차순 정렬
    @Override
    public int compareTo(Edge e) {
        return this.w - e.w;
    }
    
}

 

🎓 배운 것

1. 크루스칼 알고리즘 외워가는 중...