섬 연결하기

문제설명

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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

 

 

---

입출력 예

---

입출력 예에 대한 설명

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

---

풀이

MST(최소비용신장트리)를 찾는 문제로 크루스칼 알고리즘을 사용하면 된다. 알고리즘은 아래와 같다.

1. cost에 따라 오름차순으로 정렬한다
2. cost가 낮은 경로부터 n-1개의 경로가 생길 때까지 선택한다(n개의 vertex를 모두 연결되도록 하는 최소 edge의 갯수는 n-1개이므로)
3. 사이클이 생기지 않도록 한다

3번을 어떻게 검출하는지가 관건이다. 내가 사용한 방법은 이러하다.

먼저 parent라는 리스트를 만들어 0~n-1까지의 수를 집어넣는다. 그리고 연결이 될 때마다 parent라는 수를 갱신하는데 이 때 연결하는 두 vertex의 parent값 중 작은 값으로 갱신한다. 주의할 점은 small_parent로 갱신한 뒤에 아직 parent의 값이 big_parent인 것들도 역시 small_parent로 갱신해주어야 한다. 왜냐하면 parent가 big_parent인 노드와 small_parent인 노드를 연결하기 이전에 parent가 big_parent인 노드와 연결된 노드가 있을 수 있기 때문이다. 이 부분이 키포인트이다!!! 

def solution(n, costs):
    
    answer = 0
    cnt = 0
    parent = [i for i in range(n)]
    s_costs = sorted(costs, key=lambda x : x[2])
    for path in s_costs:
        if cnt == n-1:
            break
        if parent[path[0]] == parent[path[1]]:
            continue
        answer+=path[2]
        cnt += 1
        small_parent = min(parent[path[0]],parent[path[1]])
        big_parent = max(parent[path[0]],parent[path[1]])
        parent[path[0]] = small_parent
        parent[path[1]] = small_parent
        for i in range(len(parent)):
            if parent[i]==big_parent:
                parent[i]=small_parent

    return answer