백준 1647번 파이썬 문제풀이(도시 분할 계획) - (크루스칼)

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

1647번: 도시 분할 계획

---

간단히 크루스칼 코드만 알고 있다면 쉽게 해결할 수 있다. 조건 2가지 ( 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. , 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.) 가 있는데 그 중 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 의 조건을 생각하기가 까다로울 수 있다. 

 

문제를 잘보면 한 마을안에는 최소 1개의 집이 존재해야한다고 한다. 반대로 생각해보면 집을 1개만 남겨도 된다는 뜻이다. 따라서 크루스칼로 최소신장 트리를 만들면서 마지막에 연결되는 길만 없애주면 무조건 마을 2개를 만들 수 있으며 최소길이로 만들 수 있다.

 

import sys

input = sys.stdin.readline


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


def union_(a, b):
    a = find(a)
    b = find(b)

    # 이미 부모가 같다면 리턴
    if a == b:
        return

    if rank[a] > rank[b]:
        parent[b] = a
    elif rank[a] < rank[b]:
        parent[a] = b
    else:
        parent[a] = b
        rank[b] += 1


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

graph = []
parent = [i for i in range(N + 1)]  # 부모를 저장
rank = [0] * (N + 1)  # 각 노드마다 랭크를 저장
for i in range(M):
    a, b, cost = map(int, input().split())
    graph.append((a, b, cost))

graph.sort(key=lambda x: x[2])  # 마을의 비용을 오름차순으로 정렬
ans = 0  # 연결된 마을 길이의 합
end_v = 0  # 마지막에 연결된 마을 길이를 저장
for i in graph:

    if find(i[0]) != find(i[1]):
        union_(i[0], i[1])
        ans += i[2]  # 마을의 연결 비용들을 계속 더해주고
        end_v = i[2]  # 마지막에 연결된 마을 연결 비용을 저장

print(ans - end_v)  # 마지막에 연결된 연결 비용만 빼준 체 출력