[백준][실버 2] 11725. 트리의 부모찾기

11725. 트리의 부모찾기

11725번: 트리의 부모 찾기

• 내 풀이
  • 시간 초과

from collections import defaultdict

N=int(input())
lst=defaultdict(list)
result=defaultdict(list)
start=1
stack=[]
visited=[]
for _ in range(N-1):
    x,y=map(int,input().split())  
    lst[x].append(y)
    lst[y].append(x)

def dfs(stack, start, visited):
    stack=[start]
    while stack:
        s= stack.pop()
        if s not in visited:
            visited.append(s)
            for ls in lst[s]:
                if ls not in visited:
                    result[ls]=s #자식인덱스 부모삽입
                    stack.append(ls)

dfs(stack, start, visited)

#defaultdict 라서 value로 가져와야함
for i in range(2,N+1):
    print(result[i])

 

• 다시풀기
  • parent값이 입력되었는지 안되었는지로 visited 대신함

from collections import deque
from collections import defaultdict

N=int(input())
parent=1

stack=deque()
lst=defaultdict(list)
result=defaultdict(list)

for _ in range(N-1):
    x,y=map(int,input().split())  
    lst[x].append(y)
    lst[y].append(x)

def dfs(stack,parent):
    stack=[parent]
    result[1]=1
    while stack:
        s=stack.pop()
        for ls in lst[s]:
            if result[ls]==[]:
                result[ls]=s
                stack.append(ls)
                        
dfs(stack,parent)

#defaultdict 라서 value로 가져와야함
for i in range(2,N+1):
    print(result[i])