[BOJ/Python] 백준 1647 도시 분할 계획

문제

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

풀이

풀이 1

• 272024 KB, 3336 ms

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 4)

def findset(x):
    if p[x] != x :
        p[x] = findset(p[x])
    return p[x]

n, m = map(int, input().split()) # 집의 개수 n, 길의 개수 m
nodes = [list(map(int, input().split())) for _ in range(m)]

# 1. 비용에 따라 정렬
nodes.sort(key = lambda x : x[2])

# 2. make set
p = [x for x in range(n + 1)]

# 같은 집합 아니면 합치기
pick = 0
ans = 0

for h1, h2, cost in nodes :
    px = findset(h1)
    py = findset(h2)

    if px != py :
        p[py] = px
        pick += 1
        ans += cost

    if pick == n - 2 : break # 분리되어야 하므로 가중치 가장 큰 것만 빼고 구함

print(ans)

풀이1 설명

• 크루스칼 알고리즘으로 풀이

• 도로를 연결하면 유지비가 들고, 최소 비용을 찾고 있음

  -> MST에서 가장 비용이 높은 부분만 분리하기 !!

배운 점

PS

• MST 구하는데 둘로 분리할 때 : 가장 가중치 높은거만 분리되도록 n - 2개 구하기

Python

• sort에 key 정하기 : list.sort(key = lambda x : x[2]) … (-> sorted랑 같음 !!)