[백준1647&파이썬] 크루스칼 알고리즘을 이용한다면 최소신장트리(MST)를 찾을 수 있다.

# 문제

백준 1647 도시분할 계획 파이썬 풀이

 

1647번: 도시 분할 계획

# 코드

'''
  - 마을을 두개로 분리해야한다.
    - 마을을 두개로 분리할때, MST로 만들고 간선 하나를 떼버리면 마을이 두개로 분리된다.
    - 그렇다면 가장 큰 값을 가진 간선을 떼버리면 되지 않을까
'''
import sys
from heapq import *

N, M = map(int, sys.stdin.readline().split())  # N : 집의 개수, M : 길의 개수
edges = list()

parent = [i for i in range(N + 1)]
rank = [1] * (N + 1)


def find(node):
  if parent[node] == node:
    return node
  parent[node] = find(parent[node])
  return parent[node]


def union(nodeA, nodeB):
  a = find(nodeA)
  b = find(nodeB)

  if a == b:  # 아무것도 할 필요가 없다.
    return

  if rank[a] < rank[b]:
    parent[a] = b
  else:
    parent[b] = a
    if rank[a] == rank[b]:  # 같으면
      rank[a] += 1


for _ in range(M):
  a, b, c = map(int, sys.stdin.readline().split())
  # print(c,a,b)
  heappush(edges,(c, a, b))

# 크루스칼을 통해서 MST를 구한다
cnt = 0
result = 0
mmax = 0
while True:
  if cnt == N - 1 :  # 종료조건
    break
  cur = heappop(edges)  # ( weight, a , b  )
  # print(cur)
  if find(cur[1]) != find(cur[2]):  # 같은 집합이 아니라면
    # print("👆👆pop👆👆")
    union(cur[1], cur[2])
    mmax = max(mmax,cur[0])
    result += cur[0]
    cnt += 1

# print(parent)
print(result-mmax)

# 풀이

• 문제에서 요구하는 출력은 마을을 두개로 분리된 상태에서의 간선들의 총합이 가장 작을때이다.
• 크루스칼을 이용해서 현재 연결된 마을의 MST를 구한다. 그리고 거기서 가장 큰 간선을 빼버린다면, 간선의 합이 가장 작은 경우일 것이다.
• 크루스칼 알고리즘은 MST(최소신장트리)를 구할 수 있다. 크루스칼알고리즘은 가장 작은 간선(edge)들을 하나씩 뽑아서 선택하되 그 간선이 선택됐을때 사이클이 생기면 안된다. 그렇기 때문에 사이클 여부는 union-find를 사용하여 최적화 한다.
• 크루스칼 알고리즘의 간선을 pop하는 과정을 최적화 하기 위해서 최소힙을 사용했다. 힙을 사용하는 경우 시간복잡도는 O(m*logn)이고 퀵소트를 사용하는 경우에는 O(m*logm)이기 때문에 힙이 더 빠르다고 한다.
• union-find에서 find시 부모노드와 바로 연결시키는 것과 더불어 rank를 사용하는것을 손에 익게 하자.