[BOJ/백준] 1647번 도시 분할 계획 - Python/파이썬 [해설/풀이]

📌 문제

---

📝 입력

---

💻 출력

---

📖 예제 입출력

---

📌 풀이

---

📖 해설

---

최소 스패닝 트리 = 최소 신장 트리
가장 적은 비용으로, 사이클 없이, 모든 정점을 연결하는 알고리즘

간선이 많으면 프림 알고리즘(Prim Algorithm) 사용
간선이 적으면 크루스칼 알고리즘(Kruskal Algorithm) 사용

본 문제에서는 크루스칼 알고리즘(Kruskal Algorithm)을 사용
크루스칼 알고리즘(Kruskal Algorithm)의 핵심은 Union-Find 알고리즘

쉽게 설명하면, 자기자신을 root 노드로 초기화하고
가중치가 작은 노드부터 각각 차례대로, 하나의 집합에 추가하며
집합에 추가된 노드는 집합 내 root 노드를 부모노드로 갱신한다.

즉, 아직 집합에 추가되지 않은 노드의 부모노드가,
이미 집합의 root 노드와 동일하다면, 사이클이 존재한다고 판단

본 문제는 최소 신장 트리 문제의 응용으로,
신장 트리의 특성 상, 연결된 단 하나의 간선만 끊으면,
2개의 신장 트리로 나눌 수 있다는 특성을 이용하여,
전체 신장 트리에서 가장 긴 간선을 제거하는 방법을 사용한다.
단, 입력시간 때문에 시간초과가 발생하므로, input() 대신 readline()을 사용한다.

💻 전체코드

---

import sys
input = sys.stdin.readline

def find(n):
    if parent[n] != n:                  # 노드 n의 부모노드가 자기자신이 아니면
        parent[n] = find(parent[n])     # 노드 n의 부모노드 = 최상위 부모노드 탐색 재귀함수
    return parent[n]                    # 현재노드 n의 최상위 부모노드 return

def union(a, b):
    a = find(a)         # 노드 a의 최상위 노드 탐색
    b = find(b)         # 노드 b의 최상위 노드 탐색
    if a < b:           # a < b 이면
        parent[b] = a   # 노드b의 부모노드 a로 갱신
    else:               # a > b 이면
        parent[a] = b   # 노드a의 부모노드 b로 갱신


N, M = map(int, input().split())

edges = []
parent = list(range(N + 1))
for _ in range(M):
    A, B, C = map(int, input().split())
    edges.append((A, B, C))
edges.sort(key=lambda x: x[2])

answer = 0
last_edge = 0
for a, b, c in edges:
    if find(a) != find(b):
        union(a, b)
        answer += c
        last_edge = c
print(answer - last_edge)