글 읽기 - 덱이 큐보다 더 가볍나요?

waroad 3년 전 0

아래 코드에서 deque 대신 queue를 썼더니 시간초과가 나더라고요.

오히려 큐가 덱보다 가벼울 줄 알았는데 왜 이런 결과가 나오는 걸까요?

import sys
import math
from collections import deque
N=int(input())
arr1=[[-1 for i in range(20)]for j in range(N)]
arr1[0][0]=0
rank=[-1]*N
arr=[[]for _ in range(N)]
rank[0]=0
for i in range(0,N-1):
    tmp = [int(x) for x in sys.stdin.readline().split()]
    arr[tmp[0]-1].append(tmp[1]-1)
    arr[tmp[1]-1].append(tmp[0]-1)
que=deque()
que.append(0)
while que:
    t=que.popleft()
    for el in arr[t]:
        if arr1[el][0]==-1:
            arr1[el][0]=t
            que.append(el)
            rank[el]=rank[t]+1
arr1[0][0]=-1

for i in range(1,20):  # 부모 노드 2^i 형식으로 저장하기
    for j in range(1,N):
        if arr1[j][i-1]!=-1:
            arr1[j][i]=arr1[arr1[j][i-1]][i-1]
M=int(input())
ans=[]
for i in range(0,M):
    tmp = [int(x) for x in sys.stdin.readline().split()]
    tmp[0]-=1
    tmp[1]-=1
    if rank[tmp[0]]>rank[tmp[1]]:  # 높이 맞춰주기
        while rank[tmp[0]]!=rank[tmp[1]]:
            tmp[0]=arr1[tmp[0]][int(math.log2(rank[tmp[0]]-rank[tmp[1]]))]
    else:
        while rank[tmp[0]] != rank[tmp[1]]:
            tmp[1] = arr1[tmp[1]][int(math.log2(rank[tmp[1]] - rank[tmp[0]]))]
    if tmp[0]==tmp[1]:
        ans.append(str(tmp[0]+1))
        continue
    while True:  # 두 노드의 제일 높은 다른 조상 두 개로 업데이트 하여 바로 위 조상이 같을 때까지 돌리기
        if arr1[tmp[0]][0] == arr1[tmp[1]][0]:
            ans.append(str(arr1[tmp[0]][0]+1))
            break
        for j in range(1,16):
            if arr1[tmp[0]][j]==arr1[tmp[1]][j]:
                tmp[0]=arr1[tmp[0]][j-1]
                tmp[1]=arr1[tmp[1]][j-1]
                break
for i in range(0,M):
    print(ans[i])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

덱이 큐보다 더 가볍나요?

waroad 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말