[백준 1197 / Python(파이썬)] 최소 스패닝 트리
문제 풀이
- 크루스컬 알고리즘(Kruskal Algorithm) 이용
- 알고리즘을 이용하여 가중치의 크기를 구한 뒤 print해준다.
틀린 풀이: 시간 초과
#최소 스패닝 트리
import sys
V, E = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]
arr.sort(key=lambda x: x[2])
uf = [i for i in range(V+1)] #union-find
def kruskal():
global V, E, arr, uf
mst = 0 #최소 스패닝 트리의 가중치를 담음
for u, v, w in arr:
if find(u) != find(v):
mst += w
union(u, v)
return mst
def union(x, y):
global uf
X, Y = find(x), find(y)
uf[X] = Y
def find(x):
global uf
if uf[x] == x:
return x
return find(uf[x])
print(kruskal())
맞은 풀이
union함수의 역할을 하는 코드를 kruskal 함수 내부에 넣어줌
#최소 스패닝 트리
import sys
V, E = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]
arr.sort(key=lambda x: x[2]) #가장 뒤에 있는 가중치의 값으로 오름차순 정렬
uf = [i for i in range(V+1)] #union-find. 부모루트를 담음
def kruskal():
global V, E, arr, uf
mst = 0 #최소 스패닝 트리의 가중치를 담음
for u, v, w in arr:
A = find(u)
B = find(v)
if A != B: #사이클이 돌면 안 됨
if A > B: uf[A] = B #union함수의 역할
else: uf[B] = A
mst += w
return mst
def find(x): # x 노드가 포함된 집단의 루트 노드를 찾음. 그 집단의 대표 번호
global uf
if uf[x] == x:
return x
return find(uf[x])
print(kruskal())
'Algorithm study' 카테고리의 다른 글
[백준 1260 / Python(파이썬)] DFS와 BFS (0) | 2022.10.04 |
---|---|
[백준 1700 / 파이썬(Python)] 멀티탭 스케줄링 (0) | 2022.07.28 |
[백준 14179/파이썬(Python)] 빗물 (0) | 2022.07.18 |
CH 06. 스택(Stack) (0) | 2022.03.24 |
Ch 05. 큐(Queue) (0) | 2022.03.24 |