백준 11725번: 트리의 부모 찾기 (파이썬)

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

11725번: 트리의 부모 찾기

 

문제

 

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

 

입력

 

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

 

출력

 

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

 

풀이

 

입력 받은 트리 정보를 어떤 자료 구조를 사용하여 어떻게 표현하는지가 관건인 문제였다. 처음에는 n*n 크기의 인접행렬을 사용했더니 메모리 초과가 발생하였고, 인접한 노드들만 저장하도록 구조를 바꾸어 주었다. 이후에는 일반적인 bfs와 동일하게 문제를 해결하였다.

 

소스 코드

 

import sys
from collections import deque

n = int(sys.stdin.readline())
adjs = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = list(map(int, sys.stdin.readline().split()))

    adjs[a].append(b)
    adjs[b].append(a)

parent = [-1 for _ in range(n+1)]
parent[1] = 1

q = deque([1])
while q:
    p = q.popleft()

    for adj in adjs[p]:
        if parent[adj] == -1:
            q.append(adj)
            parent[adj] = p

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