백준 1197 최소 스패닝 트리
중요 idea:
- edgelist.append((edge, V1, V2))
- edge.sort(key=lambda x:x[0])
(간선, 노드1, 노드2) 로 입력받고, 간선을 오름차순으로 정렬 해놓는다.
-> 입력값에 1 2 10 // 2 1 1 등 이상한 테스트케이스 방지해서 최소 스패닝트리를 충족시키기 위해.
-
find(V)
-> 부모노드 누구인지 재귀적으로 확인, 초기값은 자기자신.
-> 경로 압축 스킬
-> parent[i] = find(parent[i])
-> 참고로 return 값으로 재귀를 돌리면 더오래걸린다. -
union(V1, V2)
-> parent = [ 0, 1, 2, . . . V]
노드가 1~V 까지 있으므로, parent 배열을 만들어놓고, 연결된 노드가 있을 때마다 작은 값을 부모 노드로 최신화시킨다.
import sys
V, S = map(int, sys.stdin.readline().split())
edge = []
for _ in range(S):
a, b, w = map(int, sys.stdin.readline().split())
edge.append((w, a, b))
edge.sort(key=lambda x: x[0])
parent = list(range(V + 1))
# range 1~ 안댐
def connect(a, b): # union(V1, V2)
a = check(a)
b = check(b)
if b < a:
parent[a] = b
else:
parent[b] = a
def check(a): # find(V)
if a == parent[a]:
return a
parent[a] = check(parent[a]) # 경로 압축
return parent[a] # check(parent[a])
sum = 0
for w, s, e in edge:
if check(s) != check(e):
connect(s, e)
sum += w
print(sum)
Author And Source
이 문제에 관하여(백준 1197 최소 스패닝 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@stthunderl/백준-1197-최소-스패닝-트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)