[알고리즘 고득점 kit][Level 3] 섬 연결하기

문제 설명

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

 

 

Union-Find 알고리즘

- 유니온 파인드 알고리즘이란, 어떤 두 노드가 연결되어 있는지를 판별하는 알고리즘이다.

- 서로소 집합, 상호 배타적 집합이라고도 한다.

- 노드를 합치는 union 연산, 노드의 루트 노드를 찾는 find 연산으로 이루어 진다.

 

parent 노드를 저장하는 배열이 아래와 같다.

1	2	3	4	5	6
1	1	3	4	4	5

 

2번 노드의 루트노드를 찾는 과정

    1) 배열 2번에 있는 값을 확인한다. -> 1번

    2) 배열 1번에 있는 값을 확인한다. -> 1번

    3) 배열의 인덱스 값과 일치하므로, 1번 노드가 2번노드가 속해 있는 트리의 루트노드이다.

 

6번 노드의 루트노드를 찾는 과정

    1) 배열 6번에 있는 값을 확인한다. -> 5번

    2) 배열 5번에 있는 값을 확인한다. -> 4번

    3) 배열 4번에 있는 값을 확인한다. -> 4번

    4) 배열의 인덱스 값과 일치하므로, 4번 노드가 6번노드가 속해 있는 트리의 루트노드이다.

 

만약, 4번 노드와 5번 노드가 연결되어 있는가?를 확인하려면, 루트노드가 동일한지를 확인하면 된다. 이러한 과정은 재귀함수로 구할 수 있고, 유니온파인드의 find 연산이라고 한다. 아래는 예시 코드이다.

def isFind(k, parent):
	if parent[k] == k: # 배열의 인덱스와 값이 동일하면 k는 루트 노드
    	return k
    else: # 동일하지 않으면 재귀 처리
    	return isFind(parent[k], parent)

 

그렇다면, union 연산은 어떻게 하는걸까?

위 배열에서 1번 노드와 5번 노드를 연결하고 싶다고 하자. 두 노드는 루트 노드가 다르기 때문에, 연결되어 있지 않다.

따라서, 5번의 루트노드인 4번을 1번과 연결해주면 된다. 아래는 예시 코드이다.

parent[isFind(v2, parent)] = v1

 

 

위 알고리즘 개념을 바탕으로, 섬 연결하기를 풀 수 있다.

def isFind(k, parent):
    if parent[k] == k: # 배열 인덱스와 같다면, 루트 노드임
        return k
    else:
        return isFind(parent[k], parent) # 재귀
    
def solution(n, costs):
    answer = 0
    parent = [i for i in range(n)]
    costs.sort(key = lambda x: x[2])
    link = 0
    for v1, v2, w in costs:
        if isFind(v1, parent) != isFind(v2, parent):
            parent[isFind(v2, parent)] = v1
            answer += w
            link += 1
        if link == n-1:
            break
                             
    return answer