[BOJ] 트리의 부모 찾기

---

코드

import sys
import collections
input = sys.stdin.readline

# 트리 입력
N = int(input())
tree = [[] for _ in range(N+1)]
visited = [False] *(N+1)
parent = [0]*(N+1)

for _ in range(N-1):
    n1, n2 = map(int, input().split())
    # 인접 노드 리스트에 추가
    tree[n1].append(n2)
    tree[n2].append(n1)

# BFS로 각 정점을 방문하며 부모 노드를 갱신
q = collections.deque()
q.append(1)
while q:
    v = q.popleft()
    visited[v] = True
    for adj in tree[v]:
        if visited[adj] == False:
            parent[adj] = v
            q.append(adj)

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

결과

풀이 방법

• 리스트나 딕셔너리를 사용하여 인접노드리스트 방식으로 트리를 표현한 다음, BFS나 DFS 방식으로 트리의 정점부터 인접 노드들을 탐색하면서 부모 노드를 갱신해나갔다.

---