say repository

최소 신장 트리 (MST)을 구할 경우1. 크루스칼 알고리즘 (union find 활용)2. 프림 알고리즘 프림 알고리즘1. 우선순위 큐 ( heapq ) 활용2. 우선순위 큐에 (가중치, 시작점) push3. 간선-1 만큼 우선순위큐 popimport heapq# MST (최소 신장 트리 )# 1. 크루스칼 알고리즘 ( UNION FIND 알고리즘)# 2. 프림 알고리즘# 프림 알고리즘def prim(start): visited = [False]*(n+1) # 방문처리 sum_w = 0 # 우선순위큐 (가중치, 시작점) heap = [] heapq.heappush(heap,(0,start)) cnt = 0 while heapq and cnt

유니온 파인드란?유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘Union 연산 : 노드를 합친다. (루트 노드가 더 작은 노드로)Find 연산 : 노드의 루트노드 찾는다.Union - Find 과정1. parent [] 루트 노드를 가리키는 리스트 만들어 각 노드가 자신을 가리키도록 초기화2. union(1,2) 연산 -> 1과 2의 루트 노드를 찾는다.합칠 때는 루트 노드가 더 작은 쪽으로 합치며 노드 1이 루트 노드가 더 작기 때문에 parent 리스트에서 2의 루트 노드를 노드 1의 루트노드 1로 바꿔준다.# union find 알고리즘# find 연산 : 루트 노드 찾기def find(x): if parent[x] != x: parent[x..