BOJ - 11725

백준 문제 링크
트리의 부모 찾기

❓접근법

1. BFS를 사용했다.
2. 자식 노드에 방문하지 않았다면, 현재 확인하는 노드가 부모노드이므로
   해당하는 answer의 인덱스에 부모노드의 값을 넣어준다.
3. 2번 노드부터 순서대로 출력이므로, answer[2:]를 출력하면 된다.
4. 코드는 아래 사진으로 이해하면 쉬울 것 같다.

👌🏻코드

from collections import deque
import sys

N = int(sys.stdin.readline())

lst = [[] for _ in range(N+1)]

visited = [False] * (N+1)

answer = [0] * (N+1)


for _ in range(N-1):
    x,y = map(int, sys.stdin.readline().split())
    lst[x].append(y)
    lst[y].append(x)    
    
def bfs(v):
    queue = deque()
    queue.append(v)
    while queue:
        v = queue.popleft()
        for i in lst[v]:
            if not visited[i]:
                answer[i] = v
                visited[i] = True
                queue.append(i)
            
            
bfs(1)       

for i in answer[2:]:
    print(i)

이번에도 시간초과 문제 때문에 import sys를 사용했다.