미소를뿌리는감자의 코딩
[백준 2024/02/19] 1647번 도시 분할 계획 본문
728x90
https://www.acmicpc.net/problem/1647
1. 접근 방법
이번 문제는 요점을 잘 파악하면 은근히 쉬운 문제인 것 같다.
prim's Algorithm에 대한 설명은 아래에 잘 나와 있다.
https://potatoscatteringsmile.tistory.com/112
우선 모든 노드들을 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))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/02/20] 1244번 스위치 켜고 끄기 (0) | 2024.02.20 |
---|---|
[백준 2024/02/19] 16398번 행성 연결 (1) | 2024.02.19 |
[백준 2024/02/19] 13905번 세부 (0) | 2024.02.19 |
[백준 2024/02/17] 1068번 트리 (0) | 2024.02.17 |
[백준 2024/02/15] 2606번 바이러스 (0) | 2024.02.15 |