[백준] 1647. 도시 분할 계획 (파이썬/Python)

AirPlaneMode·2021년 12월 29일
0

백준

목록 보기
5/13

문제 출처

문제

본 문제는 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에서 뽑을 때는 방문 노드가 되어있는 경우"가 있을 수 있기 때문이다.

0개의 댓글