글 읽기 - Python 시간초과 문제, 왜 PyPy로는 맞다고 나오나요?

swpaek 3년 전 0

연결된 정점 두개를 딕셔너리에 저장 한 뒤,

BFS를 사용하여 각 노드들의 부모노드를 새롭게 설정하는 방법으로 풀었습니다.

시간복잡도가 O(N)인것 같아 왜 시간초과가 나는지 궁금하여 "자주 틀리는 요인"에 들어가보니,

PyPy로 돌리라는 글을 읽고 돌려보니 답이 맞게 나왔습니다.

왜 Python에서는 시간초과가 나고 PyPy에서는 안 나는건가요?

import collections
class Node():
    def __init__(self,data):
        self.data=data
        self.child=[]
        self.parent=None
N=int(input())
tree={}
for i in range(N-1):
    n1,n2=map(int,input().split())
    if n1 not in tree:
        tree[n1]=Node(n1)
    tree[n1].child.append(n2)
    if n2 not in tree:
        tree[n2]=Node(n2)
    tree[n2].child.append(n1)
queue=collections.deque([1])
while len(queue)!=0:
    front=queue.popleft()
    if tree[front].child==[]:
        continue
    else:
        for ch in tree[front].child:
            if ch!=tree[front].parent:
                tree[ch].parent=front
                queue.append(ch)
for i in range(2,N+1):
    print(tree[i].parent)