문제 설명

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

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

풀이

원하는 값을 얻기위해선

1. 다리의 비용을 기준으로 오름차순 정렬을 한다.
2. 섬과 섬사이에 다리가 연결될 때마다 이를 기억해야한다.
3. 다리를 연결하는 판별 기준은 다리를 연결함에 따라 섬들 사이에 통로가 순환 가능한 cycle 형태로 이루어진다면 다리를 연결하면 안된다.

이는 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위한 알고리즘 을 구현하는 것이다. 즉 최소 신장 트리(MST) 문제이므로 크루스칼 알고리즘을 이용하면 된다.

알고리즘 구현 전에 생각을 해보면서 두 노드들이 연결되어 하나의 노드가 되도록 구현하면 될 것 같았는데 크루스칼 알고리즘을 알게되어서 이를 적용했더니 매우 간단하게 해결이 되었다.
parents 배열을 통해 각 노드의 부모 노드를 가리키도록 했는데 재귀형태로 구현하면 이러한 배열이 없어도 될 것 같다.

코드(Python)

def union(parents, i1, i2):
    ex_parents = parents[i2]
    for i in range(len(parents)):
        if parents[i] == ex_parents:
            parents[i] = parents[i1]

def find(parents, i1, i2):
    if parents[i1] == parents[i2]:
        return False
    else:
        return True

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x: x[2])
    parents = [i for i in range(n)]
    
    for i1, i2, cost in costs:
        if find(parents, i1, i2):
            union(parents, i1, i2)
            answer+=cost            
            
    return answer

코드(Java)

import java.util.Arrays;

class Greedy_05_Solution {
    static void union(int[] parents, int i1, int i2) {
        int ex_parents = parents[i2];
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == ex_parents) {
                parents[i] = parents[i1];
            }
        }
    }

    static boolean find(int[] parents, int i1, int i2) {
        if (parents[i1] == parents[i2])
            return false;
        else
            return true;
    }

    public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] parents = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
        Arrays.sort(costs, (c1, c2) -> c1[2] - c2[2]);

        for (int[] island : costs) {
            if (find(parents, island[0], island[1])) {
                union(parents, island[0], island[1]);
                answer += island[2];
            }
        }
        return answer;
    }
}