[백준1647] / 도시 분할 계획 - 최소 스패닝 트리(MST)

 

백준1647

 

 

푼 날짜 : 2024.12.23

푼 문제 : [1647] / 도시 분할 계획

사용한 언어 : python

알고리즘 : 최소 스패닝 트리(MST)

 

 

접근방식 :

문제의 요구조건을 보면 

 

1. 두 개의 분리된 마을로 분할
2. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할(각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다)

 

=> 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.

 

위와 같은 조건을 만족하기 위해 내가 생각한 방법은 우선 전체를 연결한 비용을 계산한 후 비용이 가장 크게 드는 길을 끊어주는 것이다.

 

이를 위해서는 전체 비용을 계산한 후 비용이 가장 큰 길의 값을 빼주면 된다!

 

MST 알고리즘 중 Prim 방식을 활용하여 구현했다.

 

 

 

코드 :

import sys
import heapq

input = sys.stdin.readline

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

graph = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]

for _ in range(M):
    A, B, C= map(int, input().split())
    graph[A].append((B, C))
    graph[B].append((A, C))

heap = [(0, 1)]
# 전체 연결 비용, 가장 큰 비용
sum_cost, max_cost = 0, 0

while heap:
    n_cost, n_edge = heapq.heappop(heap)

    if not visited[n_edge]:
        sum_cost += n_cost
        max_cost = max(max_cost, n_cost)
        visited[n_edge] = 1

        for e, c in graph[n_edge]:
            if not visited[e]:
                heapq.heappush(heap, (c, e))

# 전체 비용에서 가장 큰 비용을 빼면 2개의 마을로 나눈게 된다.
print(sum_cost-max_cost)

 

 

 

오늘도 한 문제 해결~

뿌듯하다