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

접근

서로 연결된 노드들을 tree 리스트에 저장해주고, BFS 알고리즘을 이용하여 연결된 노드들을 차례로 탐색해준다.

1을 루트로 시작하므로 1과 연결된 노드들은 1을 부모노드로 가진다. 이를 parent 리스트를 이용하여 저장해준다. 그리고 그 노드들을 queue에 추가해준다. 계속 탐색하면서 중복을 피하기 위해 연결된 노드들 중 부모노드를 가지지 않은 노드들만 차례로 탐색하면 문제를 해결할 수 있다.

코드

import sys

n = int(sys.stdin.readline())
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)
parent = [0 for _ in range(n + 1)]
q = [1]
while q:
    now = q.pop(0)
    for i in tree[now]:
        if parent[i] == 0:
            parent[i] = now
            q.append(i)
for i in parent[2:]:
    print(i)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!