[프로그래머스/Level3] 섬 연결하기 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 크루스칼 (유니온파인드)

1. 유니온 파인드 배열을 초기화한다.
2. 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.

// == Arrays.sort(costs, (o1,o2) -> Integer.compare(o1[2], o2[2]));
Arrays.sort(costs, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {    // 값이 작은 순 정렬
        return o1[2] - o2[2];
    }
});

3. 가중치가 낮은 에지부터 연결을 시도하며, 가중치가 낮은 두 노드의 대표 노드가 다를 경우에만 연결하고 (= 유니온 파인드) 비용을 갱신한다. 

if(find(costs[i][0]) != find(costs[i][1])) {
    union(costs[i][0], costs[i][1]);
    answer += costs[i][2];
}

 

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    static int n;
    static int[][] costs;
    
    static int[] parent;
    static int answer = 0;   
    
    public int solution(int n, int[][] costs) {
        this.n = n;
        this.costs = costs;
        
        parent = new int[n];
        for(int i = 0 ; i < n ; i++) {
            parent[i] = i;
        }
        
        // == Arrays.sort(costs, (o1,o2) -> Integer.compare(o1[2], o2[2]));
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {    // 🔔 건설비용 오름차순 정렬
                return o1[2] - o2[2];
            }
        });
        
        // 🔔 크루스칼
        for(int i = 0 ; i < costs.length ; i++) {
            if(find(costs[i][0]) != find(costs[i][1])) { // 연결되어 있지 않다면 연결
                union(costs[i][0], costs[i][1]);
                answer += costs[i][2];
            }
        }
        
        return answer;
    }
    
    private static int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
    
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) parent[b] = a;
    }
}

 

 

 

➕ 다른 풀이 방식

프림을 활용한 풀이

Java - [프로그래머스]42861-섬 연결하기-Kruskal/Prim

---

💦 어려웠던 점

- 흠 플로이드 와샬로 풀려고 했는데 정답이 아니었다.. 크루스칼과 유니온 파인드 너무 오랜만이어서 생각조차 하지 못 했다... 복습복습..

 

 

🧐 새로 알게 된 내용

MST (최소 신장 트리)

- 무방향 그래프

- 간선 n-1개

- 사이클 X

- 간선들의 최소 가중치 합 구하는데 사용

 

 

크루스칼

- MST

- 그리디

- 모든 간선을 가중치 기준 오름차순 정렬하고, 간선들을 순서대로 모든 정점이 연결되기 전까지 연결

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

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

 

 

✔ 크루스칼, 프림

최소 신장 트리 (MST) - 크루스칼, 프림