[백준 / 23743] 방탈출 - Python

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

23743번: 방탈출

<풀이>

pop이 생각보다 엄청난 시간 소요가 된다는 것을 알았다.

 

크루스칼 알고리즘(Union-Find)으로 최소 신장 트리를 구하는 문제이다.

탈출구는 0번 방이라고 생각하면 문제를 푸는데 더 쉽게 이해할 수 있다.

 

0~N번까지 노드의 최소 신장 트리를 구하는 문제이다.

<전체 코드>

import sys


N, M = map(int, sys.stdin.readline().split())
parants = [i for i in range(N+1)]


def find(x):
    if x != parants[x]:
        parants[x] = find(parants[x])
    return parants[x]


def union(x, y):
    root1 = find(x)
    root2 = find(y)
    parants[root2] = root1


warps = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

escapes = list(map(int, sys.stdin.readline().split()))
for i in range(N):
    warps.append([0, i+1, escapes[i]])

warps.sort(key=lambda x: x[2])

totalTime = 0

for x, y, dis in warps:
    if find(x) != find(y):
        union(x, y)
        totalTime += dis

print(totalTime)

 

 

 

 

마지막 코드에서 처음에는 while문으로 warps에서 pop 해서 진행했다.

 

 

totalTime = 0
edges = 0

while edges!=0:
    x, y, dis=warps.pop(0)
    if find(x) != find(y):
        union(x, y)
        totalTime += dis
        edge += 1

print(totalTime)

 

 

이렇게 제출했더니 시간초과가 나왔다. 아마 pop(0)연산이 시간이 오래 걸렸기 때문인 거 같다.

 

 

 

++ 추가

 

100,000개를 단순히 탐색이랑 pop(0)으로 테스트 해봤다.

 

 

시간 차이가 이렇게 크게 날줄은 몰랐다. 시간 초과를 피하기 위해서 pop(0)을 최소화 해야겠다.

 

 

+++ 추가

 

 

pop(0)대신 deque.popleft()를 사용하니 시간이 엄청 줄어들었다.