[백준 1197 / Python(파이썬)] 최소 스패닝 트리

[백준 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())