[Python] 백준 11725번: 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

import sys
input = sys.stdin.readline


def getParents(tree, N):
    parents = [-1 for _ in range(N+1)]
    todo = [1]

    while todo:
        cur = todo.pop(0)

        for node in tree[cur]:
            if parents[node] == -1:
                todo.append(node)
                parents[node] = cur

    return parents


if __name__ == '__main__':
    N = int(input())

    tree = {i: [] for i in range(1, N+1)}
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)

    parents = getParents(tree, N)
    for i in range(2, N+1):
        print(parents[i])

우선 입력값들을 dictionary에 저장한다.

1번이 루트라고 하였으니, 1번부터 시작해서 bfs를 돌리면 된다. 가령 1의 인접노드가 [3, 5]라고 하면, parents[3], parents[5]에 1을 대입하는 식으로 말이다.

마지막으로 이것을 2부터 시작해서 출력하면 된다.