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

‘프로그래머스 코딩테스트 고득점 Kit’ 문제 입니다. 😀

문제 👉 <코딩테스트 연습 - 섬 연결하기 | 프로그래머스>

1. 문제

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

2. 풀이

Greedy 와 Union-Find 를 이용한 문제 풀이

Union-Find

Union-Find 란 여러개의 노드가 존재할 때 연결된 노드들을 같은 집합 구성원으로 묶어주는 알고리즘이다.

그림과 같이 각 노드들의 번호와 연결된 노드들이 주어졌을 때, 몇개의 집합이 있는지, 각 노드들은 어떤 노드들과 같은 집합에 있는지 판단할 때 유용하다.

그림으로 나타내면, 4번과 5번이 같은 집합인지 확일하려면 중간에 다른 노드를 몇번 거쳐야하는 단점이 있다.

이러한 단점을 보완하고자 Union-Find 는 각 집합의 대표(부모)를 정해 집합의 노드들이 대표를 가르키게 한다.

건설비용에 대한 오름차순 정렬을 위해 람다식 사용

1. 처음 섬의 대표는 자기 자신으로 한다.
2. 주어진 costs 배열을 건설비용에 대한 오름차순으로 정렬한다.
3. 건설비용이 낮은 다리부터 두 섬의 대표가 다르면 다리를 놓고 부모를 통일한다.

3. 코드

import java.util.*;
class Solution{
    public int solution(int n, int[][] costs){
        int answer = 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++) {
            // find - 두 섬의 대표가 다르면
            if (find(island, costs[i][0]) != find(island, costs[i][1])) {
                // union - 연결
                unite(island, costs[i][0], costs[i][1]);
                answer += costs[i][2];
            }
        }

        return answer;
    }

    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;  // a의 대표 b로 변경
    }
}

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋