알고리즘 _ 크루스칼 알고리즘 (MST, Union-Find)

에구마·2023년 3월 30일
0

Algorithm

목록 보기
9/17

크루스칼 알고리즘

최소비용으로 모든 노드를 연결(=최소신장트리)하기 위한 알고리즘

최소 신장 트리 : 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선 중 가중치 합이 최소가 되는 트리

핵심 개념

가중치 오름차순 정렬 + Union-Find

  • 가중치가 작은 순대로 정렬
  • 순서대로 그래프에 추가
  • 사이클을 이루는지 확인하기 위해 최상위 부모노드 저장

Union-Find 알고리즘

최상위 부모노드를 저장하고 확인하기 위해 사용. 사이클 이루는지 판별.

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])
    return parent[a]
def union(u,v):
    sp = min(find(parent[u]), find(parent[v]))
    bp = max(find(parent[u]), find(parent[v]))
    parent[bp] = sp

Q. 프로그래머스 섬 연결하기

입력 : [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]
출력 : 4

def solution(n, costs):
    answer =0
    costs.sort(key = lambda x: x[2])	## 1. 입력값 정렬
    parents = [i for i in range(n+1)]

    for x in costs:	# 각 입력에서 두 노드 순서를 정렬했다. -> union계산 필요없어짐
        x[0], x[1] = min(x[0], x[1]), max(x[0], x[1])

    def find(x):
        if parents[x] == x: return x
        else:
            parents[x] = find(parents[x])
            return parents[x]
    def union(a,b):	## 위처럼 x[0],x[1]을 정렬한 경우 필요없다.. !
        ap = find(a)
        bp = find(b)
        if ap!=bp :
            parents[bp] = ap

    for n1, n2, cost in costs:			## 2. 순서대로 최상위노드(부모)확인 ->find()
        if find(n1) != find(n2):		## 3. 부모 다른경우 두 최상위 부모중 작은값으로 갱신시키고 그래프에 추가
        	parents[find(n2)] = find(n1)
            # union(n1, n2)				
            answer +=cost
    return answer

programmers섬연결하기

Q. BOJ_11724 연결요소의 갯수

무방향 연결 그래프에서 몇개의 연결 집합이 생기는 지 계산
-> 가중치가 없다 ! = 정렬할 필요 없음

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])
    return parent[a]
def union(u,v):
    sp = min(find(parent[u]), find(parent[v]))
    bp = max(find(parent[u]), find(parent[v]))
    parent[bp] = sp
...
# 연결 집합의 갯수!를 구하려면 !!
ans = []
for i in range(1, n+1):
	ans.append(find(parent[i])) #parent배열값으로 find!
print(len(set(ans)))    #중복값 제거 후 카운트

boj11724연결요소의갯수


문제 목록
boj10451순열사이클

최단경로 - 다익스트라

최단경로 -

profile
Life begins at the end of your comfort zone

0개의 댓글