[백준] 최소신장트리 (MST) - 전력난

이번에도 MST 알고리즘 문제를 하나 풀어보고자 한다.

https://www.acmicpc.net/problem/6497

 

해당문제도 MST 관련된 문제여서, 여기까지 풀어본다면 MST에 대한 개념은 충분히 잡을 수 있을 것이라 생각이 든다.

해당 문제도 오리지널 MST 알고리즘을 통해서 풀 수 있는 문제다.

 

MST 알고리즘에 관련해서 다시한번 기억해보자.

 

1. node, edge , value가 각각 주어지는 상황에서, 최소한의 value을 이용하여 모든 노드를 하나의 그래프에 속하도록 만드는 테스크이다.

2. edge의 총 개수는 node - 1로 MST를 구성할 수 있다.

3. MST는 유니온 파인드 알고리즘을 이용해서 해결할 수 있다.

 

MST 문제를 풀때 위 내용만 기억하고 진행하면 될 것이다.

 

푸는 순서에서도 기억해야할 것이 한가지 있었다.

Greedy 하게 풀기위해 value를 오름차순으로 정리하여 하나씩 간선을 이어가며 진행하면 된다.

 

Greedy하게 접근하는것이 유니온 파인드와는 다른점이니 기억하자.

 

순서

1. value 값으로 오름차순으로 정렬한다.

2. 유니온파인드 알고리즘을 구성한다.

3. 두 노드가 같은 그래프(root노드가 같으면)면 넘어가고, 다르다면 연결한다.

 

위 3단계를 거쳐서 알고리즘을 작성하면 되므로 그렇게 어렵지 않게 MST문제를 풀 수 있을것이다.

 

 

여기서 다른분들과 속도의 차이가 조금 나서, 그 이유를 살펴본 결과 sort를 할때 value가 같은경우가 있을 것 같아 x[1]으로 추가적으로 soring을 진행했는데, 그럴필요 없었고 속도만 늦추는 상황이 발생했었다.

import sys

input = sys.stdin.readline
sys.setrecursionlimit(1000000)

while True:
  M, N = map(int,input().split())
  if M == 0 and N == 0 :
    break
  edge_list = []

  for _ in range(N):
    edge_list.append(list(map(int,input().split())))
  edge_list.sort(key = lambda x : (x[2]))

  parent = [ x for x in range(M + 1 )]

  def getParent(parent , n):
    if parent[n] == n:
      return n
    parent[n] = getParent(parent, parent[n])
    return parent[n]

  def Union(parent , n1, n2 ):
    pn1 = getParent(parent, n1 )
    pn2 =getParent(parent, n2 )

    if pn1 < pn2 :
      parent[pn2] = pn1
    else:
      parent[pn1] = pn2


  def find(parent, n1, n2 ):
    if getParent(parent , n1) == getParent(parent , n2):
      return True
    else:
      return False  

  total_sum = 0
  result = 0
  for i in edge_list:
    x,y,z = i
    total_sum += z
    
    if find(parent, x,y):
      result += z
      continue
    
    Union(parent, x, y)
    
  print(result)