[그리디] 섬 연결하기 - JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

---

맨날 어려울까봐 무서워서 피했던 크루스칼 알고리즘을 이용한 문제였다!

막상 해보니까 안어려워서 좀 당황했다;;;

이렇게 좋은 알고리즘을,,,, 진작 쓸걸 ㅠ_ㅠ

 

---

아무튼 이 문제는 크루스칼 알고리즘을 사용해서 풀면 된다!

 

 

✨ 크루스칼 알고리즘

• 그래프에서 최소 비용 신장 부분 트리(MST)를 찾는 알고리즘
• ex) 최소 비용으로 모든 섬을 연결하는 다리 건설하기

 

 

크루스칼 알고리즘 조건

크루스칼 알고리즘은 기본적으로 그리디(Greedy)한 선택을 바탕으로 알고리즘을 진행한다

1. 주어진 그래프의 모든 간선에 대해 가중치가 낮은 순으로 오름차순 정렬한다
2. 정렬된 순서대로 선택하면서, 간선의 양 끝점(노드의 집합)을 Union한다
3. 이 때 선택된 두 정점이 이미 같은 집합에 속해있다면, cycle이 발생했다고 판단하고 포함시키지 않는다

 

 

Union-Find 연산

크루스칼 알고리즘을 구현하기 위해 반드시 필요한 연산이다

• Find : x가 어떤 집합에 속해 있는지 찾는 연산
• Union : x와 y의 집합을 합치는 연산 (보통 x와 y 중 작은 값으로 합친다)

위의 두 연산을 통해서 각 노드들이 속해있는 집합을 찾고 합치며 cycle 발생 여부를 확인한다

 

 

Find 메소드

    private static int find(int x) { // 부모노드 탐색 연산
        if(parent[x] == x) {
            return x;
        }
        return find(parent[x]);
    }

• parent 배열이 각 노드들의 부모노드(집합)을 저장하는 배열이다
• 이 배열은 초기에 각 노드의 인덱스로 초기화가 된다
• 따라서 만약 x와 parent[x]가 같으면 자기 자신을 가리키고 있는거니까 바로 return하고, 아니라면 다른 집합에 속해있는 것이므로 재귀호출을 통해 부모 노드를 찾아간다

 

Union 연산

    private static void union(int x, int y) { // 부모 노드 합집합 연산
        x = find(x);
        y = find(y);
        if(x>y) {
            parent[x] = y;
        } else {
            parent[y] = x;
        }
    }

• x와 y의 부모 노드(집합)을 각각 찾아준다 -> find()
• 그리고 둘 중 작은 값으로 집합을 합쳐준다
• 이는 작은 값으로 합쳐주는 것이 효율성 측면에서 좋아서 이렇게 구현한다고 한다!

 

---

 

 

자바 코드)

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

public class LinkIsland {
    static int[] parent;
    public int solution(int n, int[][] costs) { // 크루스칼 알고리즘 사용
        int answer = 0;
        parent = new int[n];
        Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[2], o2[2])); // 건설 비용 기준으로 오름차순 정렬
        for(int i=0;i<n;i++) { //union set 초기화
            parent[i] = i;
        }

        for(int[] cost : costs) {
            if(find(cost[0]) != find(cost[1])) {
                answer += cost[2];
                union(cost[0], cost[1]);
            }
        }

        return answer;
    }

    private static int find(int x) { // 부모노드 탐색 연산
        if(parent[x] == x) {
            return x;
        }
        return find(parent[x]);
    }

    private static void union(int x, int y) { // 부모 노드 합집합 연산
        x = find(x);
        y = find(y);
        if(x>y) {
            parent[x] = y;
        } else {
            parent[y] = x;
        }
    }

    @Test
    public void test() {
        Assert.assertEquals(4, solution(4, new int[][]{{0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8}}));
        Assert.assertEquals(159, solution(7, new int[][] {{2,3,7},{3,6,13},{3,5,23},{5,6,25},{0,1,29},{1,5,34},{1,2,35},{4,5,53},{0,4,75}}));
    }
}

 

---

참고)

https://sskl660.tistory.com/72

[Java]크루스칼 알고리즘(Kruskal Algorithm)