문제 풀이/백준(BOJ)
[Python] 백준 1647번 : 도시 분할 계획
희조당
2022. 8. 21. 16:39
728x90
https://www.acmicpc.net/problem/1647
1647번: 도시 분할 계획
첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번
www.acmicpc.net
💡 문제 풀이
최소 신장 트리(MST) 문제이다.
크루스칼 알고리즘을 통해서 해결했다.
문제 자체는 알고리즘을 이해하고 있으면 어렵지 않으나, 도시를 분리해야 해야 하므로 마지막에 추가된 비용을 빼줘야 한다.
✔️ 느낀 점
솔직히 마지막에 왜 빼줘야 하는지 이해를 할 수 없다. 크루스칼 알고리즘 자체를 이해하는 것이 목표라서 그냥 이해하지 않고 넘어갔다.
💻 코드
import sys
input = sys.stdin.readline
def find(x):
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]
def union(x,y):
x = find(x)
y = find(y)
parent[y] = x
N, M = map(int, input().split())
parent = list(range(N+1))
edges = []
for _ in range(M):
a, b, c = map(int, input().split())
edges.append((a,b,c))
edges.sort(key=lambda x:x[2])
cost, lastChild = 0, 0
for v1, v2, c in edges:
if find(v1) != find(v2):
union(v1,v2)
cost += c
lastChild = c
print(cost - lastChild)