1647 - 도시 분할 계획
정보
- 문제 보기: 1647 - 도시 분할 계획
- 소요 시간: 12분 14초
- 풀이 언어:
python
- 체감 난이도: 2️⃣~3️⃣
- 리뷰 횟수: ✅
풀이 키워드
스포주의
그래프
최소스패닝트리
유니온파인드
풀이 코드
정보
- 메모리: 199932 KB
- 시간: 3032 ms
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
parent = []
def union(a, b):
global parent
pa = find(a)
pb = find(b)
if pa < pb:
parent[pb] = pa
else:
parent[pa] = pb
def find(x):
global parent
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def solution():
global parent
n, m = map(int, input().split())
parent = [x for x in range(n+1)]
graph = []
for _ in range(m):
a, b, weight = map(int, input().split())
graph.append((weight, a, b))
path = []
graph.sort()
for data in graph:
weight, a, b = data
if find(a) != find(b):
union(a, b)
path.append(weight)
print(sum(path) - max(path))
if __name__ == '__main__':
solution()
풀이 해설
path = []
graph.sort()
for data in graph:
weight, a, b = data
if find(a) != find(b):
union(a, b)
path.append(weight)
다음과 같이 크루스칼 알고리즘으로 MST를 생성하고,
print(sum(path) - max(path))
분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다.
분리된 두 마을 간에는 간선이 필요 없으므로, MST의 간선 중 가장 가중치가 큰 값을 하나 빼면 답이 된다.
마을에는 집이 하나 이상 있어야 한다.
다만 최소 하나의 집이 있어야 마을로 정의되는데,
어떤 간선을 쳐내든 분할된 마을의 형태는 모두 최소 하나의 집을 가지게 되므로, 딱히 까다로운 조건은 아니다.