문제

섬 연결하기

접근

최소신장트리를 찾는 문제이다.
주어진 그래프에서 최소 비용으로 트리를 만들면 된다.
최소신장트리 알고리즘은 크루스칼, 프림 알고리즘이 있다.

크루스칼 알고리즘의 경우 탐욕적으로 가장 가중치가 작은 간선들을 선택하며, 선택된 간선들만을 이용하여 노드들을 연결한다.
이 때 사이클이 형성되는 것을 막기위해 연결된 노드들이 집합을 이루고 있을 때, 같은 집합에 속한 노드끼리는 연결하면 안된다.
이를 위해 Union-find 알고리즘을 추가적으로 사용한다.

프림 알고리즘의 경우 정점을 바탕으로 탐색하는 방법이다.
기준 정점을 잡고, 해당 정점과 연결되있는 간선들 중 최소값을 가지는 정점을 선택하여 집합에 추가한다.
이를 정점의 개수만큼 반복하면 된다.

일반적으로 크루스칼 알고리즘이 효율이 더 좋다고 알고 있다.
크루스칼의 경우 간선 e의 개수가 시간복잡도에 영향을 준다.(O(eloge))
프림의 경우 노드의 개수가 시간복잡도에 영향을 준다.(O(n^2))

문제의 조건을 보고 더 적합한 알고리즘을 이용하면 될것같다.
이 문제는 노드가 100개가 안되므로, 그냥 프림 알고리즘을 이용하여 구현하였다.

코드

• 파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def solution(n, costs):
    costs.sort(key=lambda x:x[2])
    answer = 0
    nodeset = set([costs[0][0]])
    while n != len(nodeset):
        for i, cost in enumerate(costs):
            if cost[0] in nodeset and cost[1] in nodeset:
                continue
            if cost[0] in nodeset or cost[1] in nodeset:
                nodeset.update([cost[0], cost[1]])
                answer += cost[2]
                costs.pop(i)
                break
    return answer