[Python] 백준 1647번: 도시 분할 계획

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

1647번: 도시 분할 계획

 

import sys
input = sys.stdin.readline


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

    parent[x] = find(parent[x])
    return parent[x]


def union(x, y):
    px, py = find(x), find(y)

    if px < py:
        parent[py] = px
    else:
        parent[px] = py


if __name__ == '__main__':
    N, M = map(int, input().split())
    info = [list(map(int, input().split())) for _ in range(M)]
    info.sort(key=lambda x: x[2])

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

    total_cost = 0
    last_cost = 0
    for a, b, c in info:
        if find(a) != find(b):
            union(a, b)
            total_cost += c
            last_cost = c

    print(total_cost - last_cost)

 

크루스칼 관련 URL

https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-1197%EB%B2%88-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC

[Python] 백준 1197번: 최소 스패닝 트리

 

크루스칼 알고리즘에서 마지막으로 더한 cost를 빼주기만 하면 된다.

2개의 마을로 divide 해야하며, 두 마을을 이을 필요가 없다. 이것을 위해, 크루스칼에서 그저, 마지막 union을 해주지 않으면(마지막에 하는 union은 cost가 가장 크다.) 된다! 이것으로 이어지지 않은 2개의 집합이 이 문제의 두 개의 마을이 되는 것이다.