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

1. 문제분석

섬마다 다리를 연결하는 비용의 최솟값을 구하는 문제이다.

섬을 노드, 비용을 가중치라고 생각하면 크루스칼 알고리즘을 바로 떠올릴 수 있다.

크루스칼 알고리즘에 대해서는 나중에 글로 정리할 예정이다. 주석을 달아놨으니 이해하는데 어려움은 없을 것이다.

2. 구현

 

class Solution {
    //내가 속한 집합을 찾는 메소드
    public int find(int[] parent, int i) {
        //자기 자신을 가르킨다? -> 부모
        if (parent[i] == i) {
            return i;
        }
        //어딘가에 속해있다, 부모를 찾으러 가자.
        return find(parent, parent[i]);
    }

    //두개의 집합을 합쳐보자.
    public int[] union(int[] parent, int a, int b) {
        //각자의 부모를 가져온다.
        int parentA = find(parent, a);
        int parentB = find(parent, b);

        //만약 a의 부모가 더 작다면?
        if (parentA < parentB) {
            // b의 부모는 a에 속하게 만든다.
            parent[parentB] = parentA;
        } else {
            //a의 부모는 b에 속하게 만든다.
            parent[parentA] = parentB;
        }
        return parent;
    }

    public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] countIsland = new int[n];
        //최소 비용순으로 정렬
        Arrays.sort(costs, Comparator.comparingInt(o -> o[2]));

        //집합을 구분하는 배열 생성
        for (int i = 0; i < countIsland.length; i++) {
            countIsland[i] = i;
        }

        for (int[] cost : costs) {
            //2개의 노드의 부모가 다르다? -> 집합을 합치자(간선을 연결한다는 말임)
            if (find(countIsland, cost[0]) != find(countIsland, cost[1])) {
                //비용 추가(가중치)
                answer += cost[2];
                //두개를 합쳐주세요.
                countIsland = union(countIsland, cost[0], cost[1]);
            }
        }
        return answer;
    }
}

costs는 costs[idx][0] = 출발 노드, costs[idx][1] = 도착 노드, costs[idx][2] = 가중치로 이루어져 있다.

먼저 크루스칼 알고리즘을 적용하기 위해 가중치를 오름차순으로 정렬했다.

Comparator.comparingInt(o -> o[정렬하고 싶은 idx])를 사용하면 2차원 배열을 쉽게 정렬할 수 있다.

 

먼저 집합을 합치기 전에 각각의 집합을 생성해준다(1은 1을 가르키고, 2는 2를 가르키고..)

우리는 이미 가중치를 오름차순으로 정렬했으니 for문을 사용해 데이터를 가져온다.

가중치를 기준으로 정렬했으니 하나씩 꺼내서 사용해보자.

현재 0 -> 1로 된 상태

[0,1,1]을 보면 시작 = 0, 도착 = 1, 비용 = 1이다. 현재 0과 1은 서로소 집합인 상태이니 두 집합을 합쳐준다.

만약 서로소가 아닌데 합쳐주면 사이클이 발생한다. 이는 조건에 맞지 않는다.

 

그리고 집합의 상태를 [0,1,2,3]에서 [0,0,2,3]으로 변경된다.(1이 0을 가르키기 때문이다.)

0 -> 1 -> 3까지 된 상태.

그렇다면 위의 그림처럼 바뀐다. 0 -> 1이 된상태고 우리는 다음 값을 가져온다.

[1,3,1]을 보면 시작 = 1, 도착 = 3, 비용 = 1이다. 현재 1과 3은 서로소 집합인 상태일까?

[0,0,2,3]을 보면 알 수 있다. 1은 0을 가르키고 있고 0은 부모인 상태이다. 3은 3자신만 가진 상태다.

즉, (0,1), (3)인 상태이니 두개는 합쳐도 사이클이 발생되지 않는다.

 

집합상태는 [0,0,2,0]이 된다. (3)과 (0,1)을 합쳤으니 3의 부모는 0이 된다.

0 -> 2, 0 -> 1 -> 3이 된 상태

다음은 [0,2,2]를 보자. 시작 = 0, 도착 = 2, 비용 = 2이다.

마찬가지로 서로소 집합인지 확인한다. (0,1,3), (2)가 되므로 두개의 집합을 합칠 수 있다.

 

집합 상태는 [0,0,0,0]이 된다. 즉 현재 집합상태는(0,1,2,3)이 되고 부모는 0이다.

 

집합을 합칠 때 마다 가중치를 더해주면 최솟값이 나오게 된다.

3. 마무리

문제를 보고 그래프를 통해서 최소비용을 구하는 크루스칼 알고리즘이 떠올랐다.

대학교 자료구조 강의 때 정말 이해가 안되는 알고리즘이라 그냥 무작정 코드를 짰지만 이제는 이해를 했다.

자료구조.. 정말 싫었지만 꼭 알아야하는 강의였던 것 같다.