[프로그래머스] (Java) 섬 연결하기 (그리디/Greedy) - Union-Find, 크루스칼 알고리즘

 

 

📑 1. 문제설명

---

💡 2. 접근방식

이 문제는 너무 어려워서 스스로 풀기 힘들어서 검색의 도움을 받음.
주어진 문제는 그래프 이론의 최소 신장 트리(MST, Minimum Spanning Tree) 문제이다.
 
이 문제를 풀기 위해 필요한 전제지식

- Union-Find(유니온 파인드) 자료구조
- Kruskal's Algorithm (크루스칼) 알고리즘

 

Kruskal's Algorithm (크루스칼 알고리즘)

크루스칼 알고리즘은 위에 말한 최소신장트리(MST)를 구하는 알고리즘이다. 문제의 분류 답게 greedy알고리즘으로 결정의 순간마다 최선의 결정을 함으로서 최종적인 답을 구하는 방식으로 모든 정점을 최소 비용으로 연결할 수 있게 해준다.

크루스칼 알고리즘의 핵심은 모든 간선을 가중치 기준(여기서는 다리 개설 비용)으로 오름차순 정렬하는 것이다.

그리고 이 간선들을 순서대로 모든 정점이 연결될때 까지 연결하는 것이다. 연결은 Union-find 자료구조을 이용하여 구현할 수 있고, 사이클이 형성되지 않는 모든 정점을 병합해 주면 된다.
 

Union-Find(유니온 파인드) 정리잘된 블로그

17. Union-Find(합집합 찾기)

[JAVA] 서로소 집합(Disjoint Sets)과 연산(Union & Find)

---

코드 흐름

1. costs 배열을 다리 개설 비용이 낮은 순서부터 오름차순 정렬
2. 유니온 파인드 초기화
- 각 섬은 처음에는 독립적이므로 자기 자신을 부모로 가진다. -> parent 배열
3. 정렬된 다리 리스트를 순회하며, Union-Find로 연결 여부를 확인한다.
- 비용이 낮은 다리부터 선택하고 두 섬이 다른 집합에 있다면 섬을 연결한다. 
- 모든 섬이 다 연결될 때까지 반복한다. 
4. 모든 섬이 연결되었을 때 선택한 다리 비용을 모두 더한 값을 반환한다.
 
문제에서 주어진 예시배열 costs 을 오름차순 정렬하여
코드의 흐름대로 시각화 해 보았다. 
 
costs 배열

[[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]

costs[i][2] 기준으로 오름차순 정렬

[0, 1, 1]
[1, 3, 1]
[0, 2, 2]
[1, 2, 5]
[2, 3, 8]

 

첫 번째 반복

costs에서 [0, 1, 1] 값을 꺼낸다.  
0의 부모는 0
1의 부모는 1
부모가 겹치지 않음 -> 다리를 건설한다.
union연산으로 섬1을 섬0 집합에 통합한다. 
 
<현재 상태>
그룹 0 : [섬0, 섬1]
그룹 2 : [섬2]
그룹 3 : [섬3]

---

 

두 번째 반복

costs에서 값 [1, 3, 1]을 꺼낸다.
1의 부모는 0
3의 부모는 3
부모가 겹치지 않음 -> 다리를 건설한다.
union연산으로 섬3을 섬1 집합에 통합한다. 

<현재 상태>
그룹 0 : [섬0, 섬1, 섬3]
그룹 2 : [섬2]

---

세 번째 반복

 
costs에서 값 [0, 2, 2]을 꺼낸다.
0의 부모는 0
2의 부모는 2
부모가 겹치지 않음 -> 다리를 건설한다.
union연산으로 섬2을 섬0 집합에 통합한다. 

<현재 상태>
그룹 0 : [섬0, 섬1, 섬2, 섬3]

---

네 번째 반복

costs에서 값 [1, 2, 5]을 꺼낸다.
1의 부모는 0
2의 부모도 0이다. 
0, 1, 2는 하나의 사이클을 돈다. 
따라서 다리 건설에서 제외한다.

---

다섯 번째 반복

costs에서 값 [2, 3, 8]을 꺼낸다.
2의 부모는 0
3의 부모도 0이다.
그래프에서 0, 1, 2, 3는 하나의 사이클을 돈다. 
따라서 다리 건설에서 제외한다.
 
따라서 반복문을 모두 돌고 난 후의 최종적으로 건설된 다리는 3개이다. 
또한 문제에서 다리 건설에 드는 최소 비용을 return 하라고 했으므로 1 + 1 + 2 = 4가 된다.

 

---

⭐ 3. 정답코드

import java.util.*;

class Solution {
    // 부모를 찾는 함수 (Find 연산)
    // 경로 압축
    public int find(int[] parent, int node) {
        if (parent[node] == node) return node; // 자신이 부모라면 그대로 반환
        return find(parent, parent[node]); // 부모를 따라가며 최상위 부모 찾기
    }

    // 두 노드를 같은 집합으로 묶는 함수 (Union 연산)
    public void union(int[] parent, int node1, int node2) {
        int p1 = find(parent, node1); // 첫 번째 노드의 부모 찾기
        int p2 = find(parent, node2); // 두 번째 노드의 부모 찾기

        // 두 집합을 병합 (부모가 작은 쪽을 최상위 부모로 함)
        if (p1 < p2) {
            parent[p2] = p1;
        } else {
            parent[p1] = p2;
        }
    }

    public int solution(int n, int[][] costs) {
        int answer = 0; // 모든 섬을 연결하는 데 필요한 최소 비용 누적하는 변수
        int[] parent = new int[n]; // 유니온 파인드 배열 (각 노드의 부모 저장)

        // 초기화: 각 노드는 자기 자신이 부모로 시작함
        for (int i = 0; i < parent.length; i++) 
            parent[i] = i;

        // costs 배열을 비용(costs[i][2]) 다리건설비용 기준으로 오름차순 정렬
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] cost1, int[] cost2) {
                return cost1[2] - cost2[2]; // 비용 기준 오름차순 정렬
            }
        });

        // 비용이 낮은 다리부터 순회하며 연결 작업 진행
        for (int i = 0; i < costs.length; i++) {
            // 두 섬이 이미 같은 집합에 속해 있지 않다면 연결
            if (find(parent, costs[i][0]) != find(parent, costs[i][1])) {
                answer += costs[i][2]; // 다리 비용을 추가
                union(parent, costs[i][0], costs[i][1]); // 두 섬을 같은 집합으로 병합
            }
        }

        return answer; // 최소 비용 반환
    }
}

 

👏🏻 좋아요 가장 많이 받은 코드

람다식으로 표현한 코드

import java.util.Arrays;

class Solution
{
    public int solution(int n, int[][] costs)
    {
        int sum = 0;
        int[] island = new int[n];

        for(int i = 0; i < n; i++)
            island[i] = i;

        Arrays.sort(costs, (a, b) -> Integer.compare(a[2], b[2]));

        for(int i = 0; i < costs.length; i++)
        {
            if(find(island, costs[i][0]) != find(island, costs[i][1]))
            {
                unite(island, costs[i][0], costs[i][1]);
                sum += costs[i][2];
            }
        }

        return sum;
    }

    private int find(int[] island, int x)
    {
        if(island[x]== x)
            return x;
        return find(island, island[x]);
    }

    private void unite(int[] island, int x, int y)
    {
        int a = find(island, x);
        int b = find(island, y);
        island[a] = b;
    }
}

 

---

🐦 4. 같은 유형 문제

[프로그래머스] (Java) 체육복 (그리디/Greedy)

[프로그래머스] (Java) 조이스틱 (그리디)

[프로그래머스] (Java) 큰 수 만들기 (그리디/Greedy)

[프로그래머스] (Java) 구명보트 (그리디/Greedy)

[프로그래머스] (Java) 단속카메라 (그리디/Greedy)