본 문제는 MST(Minimum Spanning Tree)로 분류된다.
즉, 모든 집을 순회할 수 있는 길의 최소값을 구한 후, 그 중 가장 긴 길을 끊어버리면 된다.
우선 Prim's Algoritm으로 코드를 구현하였다.
import sys
import heapq as h
input = sys.stdin.readline
# 0. get input
V, E = map(int, input().split())
dic = {} # start : (end, weight)
# 1. make a dict
for _ in range(E): # edge의 개수만큼
start, end, weight = map(int, input().split())
if start not in dic.keys():
dic[start] = []
if end not in dic.keys():
dic[end] = []
dic[start].append((weight, end))
dic[end].append((weight, start))
# 2. initialization
start_node = 1
next_node = start_node
candidates = []
h.heapify(candidates)
visited = [False] * (V+1)
visited[start_node] = True
cnt = 1
result = 0
longest = 0
# 3. Prim Algorithm
while cnt < V:
for value in dic[next_node]:
h.heappush(candidates, value) # {key : from, value : (weight, to)}
while True: # 가능한 최소 노드를 찾는 작업
temp = h.heappop(candidates)
to = temp[1]
if visited[to] == False: # 가능한 최소 노드를 찾았다면
visited[to] = True # 방문했으며
weight = temp[0]
result += weight # 길을 업데이트 해주고
if weight > longest: # 가장 긴 길 업데이트
longest = weight
cnt += 1
next_node = to
break
print(result-longest)
방문한 노드의 집합에서 갈 수 있는 다음 노드를 heap
에 올린 후에, heap
에서 하나씩 뽑으면서 다음 노드가 방문했는지 안 했는지 확인한다. 만약 방문하지 않았으면 해당 노드를 선택하며, 방문했으면 heap
에서 노드를 하나씩 뽑는 과정을 반복한다.
그러나 해당 코드는 시간초과 오류가 발생했다.
본 코드는 방문한 노드의 집합에서 갈 수 있는 다음 노드를 heap
에 올리는데, 갈 수 있는 다음 노드가 이미 방문한 노드인지 방문하지 않은 노드인지 상관하지 않는다.
그렇기 때문에 만약 어떤 노드에서 100개의 노드를 갈 수 있는데, 99개의 노드를 방문했더라도 일단 heap
에는 100개의 노드를 올린다는 의미이다.
이는 굉장한 시간 낭비기 때문에 해당 코드를 다음과 같이 수정하였다.
while cnt < V:
for value in dic[next_node]:
to = value[1]
if visited[to] == False:
h.heappush(candidates, value) # {key : from, value : (weight, to)}
while True: # 가능한 최소 노드를 찾는 작업
temp = h.heappop(candidates)
to = temp[1]
if visited[to] == False: # 가능한 최소 노드를 찾았다면
visited[to] = True # 방문했으며
weight = temp[0]
result += weight # 길을 업데이트 해주고
if weight > longest: # 가장 긴 길 업데이트
longest = weight
cnt += 1
next_node = to
break
어떤 노드에서 100개의 노드를 할 수 있는데, 99개의 노드가 이미 방문 되었다면 heap
에는 한 개의 노드만 올린다.
그렇다면 heap
에 방문하지 않는 노드만 올렸는데, 왜 heappop
을 할 때 방문했는지 안 했는지 왜 또 체크하는지 의문이 생길 수 있다.
실제로 실험해보지는 않았지만 이는 "heap
에 올렸을 때에는 미방문 노드였지만, heap
에서 뽑을 때는 방문 노드가 되어있는 경우"가 있을 수 있기 때문이다.