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

문제

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

입력

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

출력

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

내 풀이

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
graph = [[] for x in range(n+1)]
parents = [0]*(n+1)

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

def BFS(start):
    queue = deque([start])
    parents[start] = 1
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if parents[i]==0:
                parents[i] = v
                queue.append(i)

BFS(1)

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

코멘트

기본적으로 DFS나 BFS를 이용해서 그래프를 탐색하는 문제이지만 "부모" 노드를 찾는 것이 이 문제에서 주요한 포인트이다. 그래서 그냥 탐색을 할 때에는 visited[i] = 1을 사용했지만 이번 문제에서는 parents[i] = v로 이번에 처음 방문한 노드에 이전에 방문한 노드의 정보를 넣어주고 이를 출력함으로써 정답을 얻을 수 있다.

References

https://www.acmicpc.net/problem/11725
https://velog.io/@kupulau/백준-11724-연결-요소의-개수