섬 연결하기

Posted on Edited on In , ,

문제정의

섬 연결하기

섬 사이를 연결하는 다리를 짓는 건설비용이 주어진다. 모든 섬을 연결하려고 할 때, 드는 건설비용의 최솟값을 구하라.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.*;

class Island implements Comparable<Island>{
    int s;
    int e;
    int v;
    public Island(int s, int e, int v){
        super();
        this.s = s;
        this.e = e;
        this.v = v;
    }
    @Override
    public int compareTo(Island arg0)
    {
        return arg0.v >= this.v ? -1 : 1;
    }
}

public class ConnectingIsland {

    //프로그래머스 문제풀이 level3 섬 연결하기
    public static int[] parent;
    public static void main(String[] args) {
        int costs[][] = {
            {0, 1, 5},
            {1, 2, 3},
            {2, 3, 3},
            {3, 1, 2},
            {3, 0, 4},
            {2, 4, 6},
            {4, 0, 7}
        };
        int n = 5;

        int answer = 0;
        parent = new int[n];
        for(int i = 0; i < n; i++)
            parent[i] = i;

        
        List<Island> list = new ArrayList<>();
        for(int i = 0; i < costs.length; i++)
        {
            Island temp = new Island(costs[i][0], costs[i][1], costs[i][2]);
            list.add(temp);
        }
        Collections.sort(list);
        
        //matrix 만들기
        for(Island land : list)
        {
            if(find(land.e) == find(land.s))
                continue;
            union(land.e, land.s);
            answer += land.v;
        }

        System.out.println(answer);
    }
    public static int find(int a)
    {
        if(a == parent[a])
            return a;
        return parent[a] = find(parent[a]);
    }
    public static void union(int a, int b)
    {
        int a_root = (find(a));
        int b_root = (find(b));
        if(a_root != b_root)
            parent[a_root] = b;
    }
    
}
크루스칼 알고리즘을 사용하면 된다. 필자는 분명 수업시간에 들었던 것 같은데 막상 구현하려고 하니 다 까먹었다.. 그래서 이번 문제를 통해 다시 정리할 수 있었다. 크루스칼 알고리즘을 간단히 설명하자면 간선의 비용이 가장 적은 것 부터 선택해 나가는 알고리즘이다. 다만 사이클이 형성되어서는 안된다. 그렇다면 간선을 선택할 때 마다 사이클이 발생하는지 봐야하는데 이 때 쓰이는 자료구조가 union-find이다.

union-find를 구현하기 위해 parent배열을 선언했다. parent 배열은 자신의 부모가 누구인지 저장하는 배열이다. 처음에는 자신의 위에 아무도 없으므로 배열의 인덱스로 값을 초기화한다.

union-find에선 두 가지 함수가 필요한데, 하나는 find함수이고, 하나는 union이다. find는 해당 노드의 최상단 부모를 찾아주는 함수이다. 최상단 부모는 parent값과 노드 값이 일치할 것이므로 그 때의 값을 반환하면 된다. 그렇지 않다면 재귀를 통해 부모를 찾아간다. 이 때, return문을 보면 find한 값을 parent[a]에 대입하는 것을 볼 수 있는데, 이 과정을 거치지 않는다면 \(O(n)\)으로 수행 시간이 길어지기 때문이다.

union함수는 두 노드를 합쳐주는 역할을 한다. a의 최상단 부모값과 b의 최상단 부모값을 찾아 이 둘이 같지 않다면 부모를 통일해준다. 코드 자체는 어렵지 않다.

필자는 섬을 표현하기 위한 클래스 Island를 새로 선언하였다. 시작점을 s, 끝점을 e, 비용을 v로 하였다. 정렬기준은 비용을 기준으로 하였다. 메인에서 읽어들인 값을 리스트에 저장하여 정렬하였다. 이렇게 하면, 간선비용을 기준으로 하여 오름차순으로 정렬 할 수 있다.

오름차순으로 정렬한 Island를 순회하며, 사이클이 형성될 경우 간선을 선택하지 않고 그렇지 않을 경우 그 값을 answer에 더하고 두 섬이 합해지는 걸 나타내기 위해 union함수를 사용한다. 사이클인지 아닌지 확인하는 방법은 두 섬의 최상단 부모가 같은지 확인하면 된다.

간선의 최대 개수는 \(n*(n-1) \over 2\)이므로, 최종 시간복잡도는 \(O(n^2log_2n^2)\)이다.

테스트



union-find를 연습했었는데 다시 하려니 또 까먹었다. 최적화하는 방법까지 잘 익혀야겠다. 중요한건 복습 또 복습이다.

다른 사람의 풀이를 보니 별도 클래스를 선언하지 않고 람다식으로 특정값을 기준으로 정렬하는 것을 보았다. 앞으로도 잘 쓰일 것 같으니 여기에 메모해 둔다.

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