[이코테](python) 그래프 _ 도시 분할 계획 (최소 신장 트리, 크루스칼 알고리즘)

🧩 문제

도시 분할 계획
(백준에 똑같은 문제가 있었군..!)

---

🧩 문제 해석

📌신장 트리

(직접 노션에 정리한 페이지)

이 문제는 전체 마을(그래프)에서 최소 2개의 신장 트리를 만드는 것이다.
최소한의 비용으로 2개의 신장 트리로 분할하는 것이 목표다.

크루스칼 알고리즘으로 최소 신장 트리를 찾은 후, 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거하면 된다. 그러면 최소 신장 트리가 2개의 부분 그래프로 나누어지며 최적의 해를 구할 수 있게 된다.

---

🏁 풀이

# 이코테 _ 그래프 _ 최소 신장 트리(크루스칼 알고리즘) _ 도시 분할 계획

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니면 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 찾기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a > b:
        parent[b] = a
    else:
        parent[a] = b

# 노드와 간선 입력받기
v, e = map(int, input().split())
# 부모 테이블 초기화
parent = [0] * (v + 1)

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블상의 원소를 자기 자신으로
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    # 비용순으로 출력하기 위해서 튜플의 첫번째 원소를 비용으로 설정
    edges.append((cost, a, b))

# 간선을 비용순으로 정렬
edges.sort()
last = 0 # 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선

# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 부모 합침
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
        last = cost # 간선을 비용순으로 정렬하였으므로 가장 마지막의 cost가 가장 비용이 큰 간선이다.

print(result - last)

---