[BOJ] 11725번 트리의 부모 찾기

백준 11725번 트리의 부모 찾기 (실버2)

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이

일단 각 정점의 부모 번호를 저장할 parent 배열을 만듭니다. 이 때 루트의 부모는 자연스럽게 0이 됩니다.

이후 BFS를 돌리면서 현재 노드와 연결되어 있는 노드를 조사합니다.
이때 next가 cur의 부모인지 확인해 만약 부모일 경우엔 건너뜁니다.
부모가 아니면 큐에 넣고 parend[next] = cur로 만들어줍니다.

visited를 사용할 때와 코드의 흐름이 크게 달라지지는 않습니다.
당연히 시간복잡도도 O(V+E)로 동일한데, 트리에서는 E = V-1이기에 그냥 O(V)가 됩니다.

이렇게 parent 배열을 사용해서 root 번호의 정점을 루트로 두었을 때 각 정점의 부모 정보를 BFS 한 번으로 알아낼 수 있습니다. 부모 정보가 필요한 문제에서는 이를 활용할 수 있습니다.

import sys
from collections import deque


def bfs(graph):
    q = deque([1])
    parent = [0] * 100001  # parent[i] = j -> i의 부모노드가 j

    while q:
        cur = q.popleft()
        for next in graph[cur]:
            # 현재 노드의 부모가 다음 노드라면
            # 즉, 다음 노드가 자식이 아니라 부모노드라면
            if parent[cur] == next:
                continue
            parent[next] = cur
            q.append(next)
    return parent


if __name__ == "__main__":
    input = sys.stdin.readline

    n = int(input())
    graph = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    parent = bfs(graph)

    for i in range(2, n + 1):
        print(parent[i])