백준 1647번 도시 분할 계획 (Python)

문제 링크

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

1647번: 도시 분할 계획

---

Test Case

---

문제 풀이

그래프 문제 중 크루스칼 알고리즘.
전체 그래프에서 2개의 최소 신장 트리를 만들어야하는데, 제일 좋은 방법은 일단 주어진 그래프를 최소 신장 트리로 만들고, 그 중에서 제일 비용이 큰 마을 사이를 빼면 문제 조건을 만족할 수 있다.

서로소 집합 개념과 크루스칼 알고리즘을 알아야 풀 수 있고 find_parent, union_parent 함수는 암기하는게 좋음

---

Source Code

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
parent = [0] * (n+1)
for i in range(1,n+1):
    parent[i] = i

edges = []

for i in range(m):
    a,b,c = map(int, input().split())
    edges.append((c,a,b))

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

edges.sort()
result = 0
last = 0
for edge in edges:
    cost,a,b = edge
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        last = cost
        result += cost

print(result-last)