1. 문제 설명

섬 연결하기

2. 문제 분석

양방향 그래프의 최소 신장 트리를 구한다. 즉 모든 정점을 연결하는 경로의 총 비용이 최소인 경로를 찾아야 한다. 크루스칼 알고리즘을 사용한다.

1. 간선의 비용 순서대로 정렬한다.
2. 순서대로 간선을 꺼내면서 총 비용을 계산한다. 이때 간선을 이루는 노드가 기존에 계산한 노드들과 사이클을 이루지 않아야 한다.
3. 사이클 유무를 검사하기 위해 Union_Find 함수를 통해 두 노드의 루트 노드가 같은지 비교한다. 즉 서로를 포함하지 않아야 한다.
4. 간선의 총 개수가 정점의 개수보다 1 적을 때 경로가 완성된다.

• find 함수는 특정 노드의 '루트' 노드를 반환한다. 이때 루트라는 말은 곧 자신의 인덱스가 자신을 가리킬 때 루트라고 할 수 있다.
• union 함수는 루트 노드가 서로 다른 서로소 관계의 두 노드를 하나로 합친다. 코드로 간단히 설명하자면 1번 노드와 2번 노드의 루트 노드(서로 다름을 미리 확인하였음)를 꺼내고, 1번 루트 노드가 2번 루트 노드를 가리키도록 (혹은 반대로) 한다.

3. 나의 풀이

def solution(n, costs):
    costs.sort(key=lambda x:x[2])
    # 최소 비용 순으로 정렬
    parent = [i for i in range(n)]
    # 루트 노드는 자기 자신을 가리키도록 초기화
    
    def find(node):
        # 주어진 노드가 루트 노드가 아니라면, 루트 노드를 찾을 때까지 거슬러 올라간다.
        while parent[node] != node:
            p = parent[node]
            node = p
        return node
        
    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        parent[root2] = root1
        # node1, node2의 루트 노드를 찾아 root1이 root2의 루트 노드가 되도록 병합
        
    total = 0
    edge_cnt = 0
    
    for cost in costs:
        if edge_cnt == n-1: break
        # 총 간선의 개수가 정점 수 -1일 때 완료
        
        node1, node2, weight = cost
        if find(node1) != find(node2):
            # 추가하려는 간선이 사이클을 만들지 않을 때
            union(node1, node2)
            total += weight
            edge_cnt += 1
            
    return total

• find 함수를 재귀가 아니라 반복 함수를 사용할 떄 직관적으로 이해하기 쉬워서 위 코드대로 구현했다.