❗ 풀이

My Code

메모리 : 54228KB
시간 : 384ms

트리 루트를 1이라고 가정 : 시작 노드

deque를 활용해서 풀이했고
입력되는 경로에 대해
graph를 만들어 서로 갈 수 있는 노드들 양방향에 서로를 넣어주고

popleft되어 나오는 노드값들 마다
갈 수 있는 노드들을 조회하는 for문을 활용해서
최초로 방문하는 노드의 부모로 자신을 넣어준 후,

도착 노드값을 다시 큐에 삽입하는 형태로 풀이하였다.

마지막으로
출력조건이
2번 노드부터 순서대로 출력하는 것이기 때문에
Parent[2:]를 사용하였다.

import sys
input = sys.stdin.readline
N = int(input())
visited = [0 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for _ in range(N-1) :
    p, c = map(int,input().split())
    graph[p].append(c)
    graph[c].append(p)
Parent = [i for i in range(N+1)]
root = 1
from collections import deque
q = deque([root])
visited[root] = 1
while q :
    node = q.popleft()
    for v in graph[node] :
        if visited[v] == 0 :
            q.append(v)
            Parent[v] = node
            visited[v] = 1
for p in Parent[2:]:
    print(p)