[백준-11725] 트리의 부모 찾기

문제

링크

코드

from collections import deque
n = int(input())

graph = [[] for _ in range(n+1)]
pnode = [0] * (n+1)
for _ in range(n-1) :
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()
    
def bfs(v, graph) :
    queue = deque()
    queue.append(v)
    while queue :
        v = queue.popleft()
        for g in graph[v] :
            if pnode[g] == 0 :
                queue.append(g)
                pnode[g] = v
    return pnode[2:]
        

for p in bfs(1, graph) :
    print(p)

풀이

먼저 입력받으면서 연결된 노드끼리 다 저장하기
트리의 루트가 1이기 때문에 1부터 시작
1과 연결된 노드들 큐에 넣고, pnode(부모 노드 저장 배열)에 1저장
while문이 돌 때
큐에 있는 노드를 하나씩 뺄 때, 해당 노드와 연결된 노드를 큐에 저장하면서
pnode에 뺀 노드를 저장하면 된다!
단, 이때 pnode에 아무런 부모 노드가 저장되지 않아야 한다.