[백준 2024/02/19] 1647번 도시 분할 계획

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

1647번: 도시 분할 계획

 

1. 접근 방법

이번 문제는 요점을 잘 파악하면 은근히 쉬운 문제인 것 같다.

prim's Algorithm에 대한 설명은 아래에 잘 나와 있다.

https://potatoscatteringsmile.tistory.com/112

[백준 2024/02/13] 1922번 네트워크 연결

 

우선 모든 노드들을 Prim's Algorithm을 이용해서 연결해준다. 이후, 가장 큰 값의 weight를 빼주면 된다.

그렇게 된다면 자연스럽게 마을이 2개로 분리가 되며, 가장 큰 weight를 빼주었으므로 유지비의 합도 최소가 될 것이다.

 

 

weight_road라는 list에 weight들을 다 저장해준 후, 

weight_road.sort()

weight_road.pop() 을 통해 최대값을 빼주었다.

 

2. 코드

import heapq

nodes, edges = map(int, input().split())

node_list = [[] for _ in range(nodes + 1)]
visited = [False] * (nodes + 1)
heap = []
weight_road = []

for i in range(edges):
    n1, n2, w = map(int, input().split())
    node_list[n1].append((w, n2))
    node_list[n2].append((w, n1))

visited[1] = True

for w, node in node_list[1]:
    heapq.heappush(heap, ( w, node))

edges_visited = 0
while edges_visited < nodes - 1:
    w, node = heapq.heappop(heap)
    if not visited[node]:
        edges_visited += 1
        weight_road.append(w)
        visited[node] = True
        for w, node in node_list[node]:
            heapq.heappush(heap, ( w, node))


weight_road.sort()
weight_road.pop()
print(sum(weight_road))