[Python] 1647 - 도시 분할 계획 (골드 4)

1. 문제 설명

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

1647번: 도시 분할 계획

 

---

2. 아이디어

[Python] 1197 - 최소 스패닝 트리 (골드4)

이전에 풀이했던 최소 스패닝 트리 풀이로 사용한 Union-find 알고리즘에서 아주 살짝 더 나갔다.

이전 포스팅에서 언급을 안 했었는데, 가중치를 기준으로 sort하고 union하는 것을 크루스칼 알고리즘이라고 한다.

이름만 들으면 되게 무시무시 해보이는데 알고리즘 자체는 귀엽다.

 

똑같이 비용 순서로 정렬하고 정점을 이어주면 된다.

마을을 두개로 분리하라니까 뭔가 엄청 복잡한 계산이 필요한가 싶지만 2~3줄만 추가하면 끝난다.

아무리 많은 간선 정보가 들어와도 Union-find로 정점을 이어주면 최종적으로 하나의 흐름으로 이어진다.

무슨 의미냐면 순환되는 Cycle이 존재하지 않는다.

 

이러한 버뮤다 지대가 존재하지 않음.

1에서 2로 이동하고, 2에서 3, 3에서 4로 갔는데 난데없이 4에서 1로 이어지는 건 불가능 하다.

따라서 Union find로 마을 전체의 길을 하나로 이어준 후에 그 중에서도 가장 비용이 많이 드는 길을

끊어버리면 도시 분할 계획은 성공적으로 이루어진다.

 

---

3. 코드

import sys

input = sys.stdin.readline

def find(num, node):
    if num == node[num]:
        return num
    return find(node[num], node)

def union(a, b, node):
    a = find(a, node)
    b = find(b, node)

    if a > b:
        node[a] = b
    elif a <= b:
        node[b] = a

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

    for _ in range(m):
        a, b, c = map(int, input().split())
        cost.append((c, a, b))
    cost.sort()
    
    for value in cost:
        c, a, b = value
        if find(a, parent) != find(b, parent):
            union(a, b, parent)
            result += c
            max_cost = c

    print(result - max_cost)
        

solution()