[이코테] CH10 그래프 이론 크루스칼 알고리즘 기본 코드

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def find_parent(parent,x):
    if parent[x]!=x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
    

v,e = map(int,sys.stdin.readline().split())
parent = [0] * (v+1) # 부모 테이블의 초기화
edges = [] # 간선을 넣어줄 새로운 배열의 형성
result = 0

for i in range(1,v+1):
    parent[i] = i # 초기에는 자기 자신을 부모 노드로 설정한다

for _ in range(e):
    a,b,cost = map(int,sys.stdin.readline().split())
    edges.append((cost,a,b))
edges.sort()

for edge in edges:
    cost,a,b = edge
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result += cost
print(result)

def find_parent

: 재귀적으로 최종적인 루트 노드가 누구인지를 탐색한다

parent[x] == x라면 ? 루트 노드라는 뜻

그때 최종적인 루트 노드가 반환된다

1 <- 2 <- 3 <- 4라면

2,3,4 모두 루트 노드가 1이 반환된다

 

def union_parent

: 큰 수가 작은 수를 가르키도록 한다 (그래서 비용을 기준으로 edges를 정렬한것도 있음)

 

find_parent(parent,a)!= find_parent(parent,b)

루트 노드가 다르다는 소리이므로 싸이클이 형성되지 않는다 -> union 실행 가능