[programmers] 섬 연결하기 (Java)

[섬 연결하기]

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

프로그래머스

 

 

[접근 방식]

- '크루스칼 알고리즘' 을 이용한다.

그래프에 가중치 기준 오름차순의 간선을 차례로 추가하면서, 최소 신장 트리를 구하는 알고리즘이다.

 

간선을 추가하며, 루트 노드를 기준으로 노드들을 하나의 집합으로 묶는다.

모든 노드가 하나의 집합이 되는 순간 '최소 신장 트리' 가 완성된 것으로 간주하고, '최소 간선 가중치 합'을 구한다.

 

1. 간선을 가중치 기준 오름차순으로 정렬한다.

 

2. 간선을 기준하는 노드들이 서로 다른 트리에 있는 경우 트리를 병합한다.

: 이를 모든 노드가 한 트리에 있을 때 까지 반복한다.

 

2-1) 간선 '[0, 1, 1]' 

node 1 이 node 0 을 루트 노드로 하는 트리에 소속된다.

누적 간선 가중치의 합은 1 이다.

 

2-2) 간선 '[0, 3, 1]' 

node 3 이 node 0 을 루트 노드로 하는 트리에 소속된다.

누적 간선 가중치의 합은 2 이다.

 

2-3) 간선 '[0, 2, 2]' 

node 2 가 node 0 을 루트 노드로 하는 트리에 소속된다.

누적 간선 가중치의 합은 4 이다.

 

이미 root node 가 같은 한 트리에 모든 노드가 소속되었기 때문에 '간선 [1, 2, 5]' , '간선 [2, 3, 8]' 은 고려하지 않아도 된다.  

 

[Java 코드]

//https://school.programmers.co.kr/learn/courses/30/lessons/42861
//코딩테스트 연습 - 탐욕법(Greedy) - 섬 연결하기

import java.util.Arrays;

class Solution {
    public int solution(int n, int[][] costs) {
        //0. '최소 간선 가중치 합'
        int sum = 0;

        //1. root node를 저장할 배열
        int[] island = new int[n];
        for (int i = 0; i < n; i++){
            island[i] = i;
        }

        //2. 간선들을 비용 기준 오름차순 정렬
        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[b] = a;
    }
}

 

[Rewind]

1. 알게된 점

- '크루스칼 알고리즘' 의 동작 방식에 대해 알게 되었다.

- 새로운 문제 해결방법을 하나 더 알게되었다.

 

2. 어려웠던 점

- 문제의 접근방식 조차 유추하지 못하였다.

- 다른 사람의 문제 해결 코드를 보고서도 'find' , 'unite' 메서드를 잘 이해하지 못하였다.

 

3. 개선 방안

- 문제를 그냥 더 많이 풀어보면서 경험을 누적시켜야 한다 라고 생각한다.