섬 연결하기 [자바]

 

🧫 문제 분석

✔️ 출처

섬 연결하기 level 3

📖 문제

 

다익스트라로 했다가 생각해보니 이건 최단경로가 아닌 최소비용으로 연결하는 거였다.

알고리즘 시간때 배웠던 걸로 기억하는데 최소신장트리 였던걸로 기억한다. 

 

서로소 집합, 유니온, find 등 같은 걸 배웠었는데 기억이 안나서 결국 찾아봤다. 

https://sskl660.tistory.com/72
자세한 이론은 위 블로그 참조 

핵심은 최소 비용으로 정렬하고 

연결하는 두 노드(섬)의 부모가 서로 달라야한다. (사이클 방지, 최소 신장 '트리' 이기에 사이클은 없어야한다. )

이때 find 메서드를 사용해서 각각 부모를 찾는다. 

두 노드의 부모가 서로 다르다면 

union 메서드를 사용해서 두 노드 중 부모가 더 작은 곳으로 편입된다. 

이때 실제 원소가 편입되는 것이 아닌 부모가 편입되는 것이다. 

 

 

사이클 발생시 문제점

불필요한 간선 추가 사용

최소 비용 보장 안됨

중복 연결 가능성

 

---

🔅 문제 풀이

import java.util.*;
import java.util.stream.IntStream;
class Solution {
    
    int[] parent;
    int final_cost;
    
    public int solution(int n, int[][] costs) {
        
        // 간선 비용 오름차순 정렬
        Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[2], o2[2]));
        // 부모 노드 초기화 (섬이 n개이므로 0~n-1번까지)
        parent = IntStream.range(0, n).toArray();
        
        // 낮은 비용부터 크루스칼 알고리즘 진행
        for (int i = 0; i < costs.length; i++) {
            if (find(costs[i][0]) != find(costs[i][1])) { // 부모가 같으면 사이클이 생기기에 방지
                union(costs[i][0], costs[i][1]);
                final_cost += costs[i][2]; 
            }
        }
    
        return final_cost;
    }
    
    // 사실상 두 집합이 합쳐진 것이 아니라 각 집합의 대표 부모가 다른 부모로 편입되는 것
    private void union(int a, int b) {
        a = find(a); // 부모 찾기 
        b = find(b);
        
        // 더 작은게 부모가 된다. 
        if (a > b) {
            parent[a] = b;
        } else {
            parent[b] = a;
        }
    }
    
    // 부모가 누구인지 찾음
    private int find(int x) {
        if (parent[x] == x) return x; // 서로소 집합으로 부모는 자기 자신을 가리킴
        return parent[x] = find(parent[x]); // 경로 압축 
    }
}

 

❗ 오답노트 / 필요한 지식

1. 알고리즘 시간에 배운것은 헛되지 않았던 것이다. 이번 기회에 크루스칼도 잘 기억하자.