크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘 (Kruskal Algorithm)

1.개념

최소 비용 신장 트리를 만드는 대표적인 알고리즘

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘

최소 비용으로 노드를 연결하려면 필요한 간선의 갯수 = 노드 - 1

Union - Find 알고리즘을 이용하여 사이클이 생기지 않도록 각 노드들을 같은 그래프에 넣기

2. 알고리즘

point -> 노드를 연결만 시키면 된다 !!

비용 기준 오름차순 정렬 후 하나씩 그래프에 포함 시킨다.

이때 사이클이 되는 경우는 제외한다.

3. 코드

프로그래머스 섬 연결하기 문제가 크루스칼 알고리즘으로 해결할 수 있어 해당 문제의 답을 코드로 첨부해보겠습니다.

def getParent(parent, x): if parent[x] == x : return x parent[x] = getParent(parent,parent[x]) return parent[x] def unionParent(parent, a,b): a = getParent(parent,a) b = getParent(parent,b) if a < b: parent[b]=a else:parent[a]=b def findParent(parent,a,b): a = getParent(parent,a) b = getParent(parent,b) if a==b: return 1 else: return 0 def solution(n, costs): answer = 0 ch=[i for i in range(n)] #각 노드를 독립적으로 놓기, 각자 노드의 부모노드는 자기 자신 costs = sorted(costs,key = lambda x: x[2]) #비용을 기준으로 오름차순 정렬 for i in costs: if not findParent(ch,i[0],i[1]): #사이클이 발생하지 않도록 같은 그래프가 아니면 그래프에 추가 answer+=i[2] # 필요한 비용 더하기 unionParent(ch, i[0],i[1]) # 그래프에 두 노드 추가 return answer if __name__ =="__main__": print(solution(4,[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]))

4. 문제

https://programmers.co.kr/learn/courses/30/lessons/42861

from http://vhrlgkwlak.tistory.com/67 by ccl(A) rewrite - 2021-09-06 00:00:38