파란색가운의 개발 블로그
[이코테] 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 실행 가능
'알고리즘 문제 풀이 > 이코테' 카테고리의 다른 글
[이코테] CH10 그래프 이론 실전문제 3번 도시 분할 계획 (0) | 2024.01.19 |
---|---|
[이코테] CH10 그래프 이론 실전문제 2번 팀 결성 (0) | 2024.01.19 |
[이코테] CH09 최단경로 실전문제 40번 숨바꼭질 (0) | 2024.01.17 |
[이코테] CH09 최단경로 실전문제 39번 화성 탐사 (0) | 2024.01.17 |
[이코테] CH09 최단경로 실전문제 38번 정확한 순위 (0) | 2024.01.17 |