[Python] BOJ 1647 - 도시 분할 계획

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

1647번: 도시 분할 계획

# 무난한 MST문제이다. 마을을 두개의 마을로 분리하면서 남은 길들의 유지비가 최소가 되어야 하므로

   크루스칼 알고리즘으로 최소 간선들로만 모든 집을 연결 한 뒤 가장 비용이 큰 길 하나만 없애면 된다.

 

# 27 ~ 31줄 반복문에서 last는 항상 g[2]로 갱신되는데 graph가 비용순으로 오름차순 정렬되어 있으므로

   결국 마지막 last에는 가장 비용이 큰 길의 비용이 들어오게 된다. 

   따라서 answer - last를 출력하면 된다.

 

import sys
input = sys.stdin.readline
def find(c):
	if par[c] == c:
		return c
	else:
		par[c] = find(par[c])
	return par[c]

def union(a, b):
	a, b = find(a), find(b)
	par[max(a, b)] = min(a, b)

# a와 b의 부모가 같은지 판단하는 함수
def check(a, b):
	return find(a) == find(b)

N, M = map(int,input().split())
par = [i for i in range(N+1)]
graph = []
answer = 0
for _ in range(M):
	a, b, c = map(int,input().split())
	graph.append((a, b, c))
graph.sort(key = lambda x: x[2])

for g in graph:
	if not check(g[0], g[1]):
		union(g[0], g[1])
		answer += g[2]
		last = g[2]
print(answer - last)

(solved.ac 티어: 골드 4)