해당 문제는 전형적인 최소 신장 트리 문제이다. 모든 노드를 연결하면서 비용을 최소로 하는 문제이기 때문이다.
최소 신장 트리를 구하는 대표적인 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 있다. 이 두 알고리즘이 그리디를 기본으로 하기 때문에 그리디로 분류된 것이다.
크루스칼 알고리즘은 신장트리에 하나씩 간선을 더해가며 만드는 방법입니다. 이 알고리즘의 핵심은 모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차례대로 그래프에 연결하는 것이다.
프림 알고리즘은 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법입니다.
구현 난이도가 쉬운 것은 크루스칼 알고리즘이다. 각 간선을 추가할 때마다 추가되는 간선이 기존에 있던 트리에서 사이클을 만드는지 검사해주면 된다. 사이클의 유무는 Union - find를 이용해 구현할 수 있다.
parents = [i for i in range(100)]
def union(a,b):
a = find(a)
b = find(b)
if a > b:
a,b = b,a
parents[b] = a
def find(a):
if a == parents[a]:
return a
parents[a] = find(parents[a]) # 이 부분 중요!
return parents[a]
def solution(n, costs):
answer = 0
costs.sort(key=lambda x : x[2])
for cost in costs:
x,y,c = cost
if find(x) == find(y):
continue
else:
answer += c
union(x,y)
return answer 