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

문제

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

입력

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

출력

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

예제 입력 1

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

4
6
1
3
1
4

예제 입력 1

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 1

1
1
2
3
3
4
4
5
5
6
6

제출 답안

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

n = int(input())
graph = [[] for _ in range(n + 1)]
parent = [[] for _ in range(n + 1)]

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

def dfs(graph, start, parent):
    q = deque([(start)])
    while q:
        node = q.popleft()
        for i in graph[node]:
            parent[i].append(node)
            q.append(i)
            graph[i].remove(node)
    return parent


for i in list(dfs(graph, 1, parent))[2:]:
    print(i[0])

1. 1부터 돌면서 dfs를 실행한다.
2. 1에 들어있는 요소들을 parent리스트에서 해당 인덱스의 값을 1로 초기화 하는 식으로 나아간다. 1이 트리 루트니깐 이거랑 1에 들어있는 요소들과 연결된 다른 요소들을 deque로 돌아가면서 찾는다.
3. 최종으로 parent를 for문 돌려서 출력한다.