백준 11725 트리의 부모 찾기

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

 

 이 문제는 노드의 개수 N이 주어지고 이후 N-1개의 노드 간 연결을 보여준다. 그리고 1을 루트로 하는 트리에서 2번 노드부터의 부모 노드를 출력하는 문제이다.

 

 이 문제는 양방향 graph를 defaultdict를 사용하여 구현하고, DFS를 이용하여 1부터 시작하여 트리를 그려나가며 부모와 자식을 저장하는 식으로 풀었다. 필자는 처음엔 재귀를 이용하여 DFS를 풀었으나, 입력 범위가 매우 넓어, 재귀오류가 일어나, 스택을 이용하여 DFS를 구현하였다

 

from collections import defaultdict as dd
import sys
input = sys.stdin.readline

def iterative_DFS(start):
    stack = [start]
    while stack:
        parent = stack.pop()
        for child in graph[parent]:
            if not visited[child]:
                ans[child] = parent
                visited[child] = True
                stack.append(child)

graph = dd(list)
N = int(input().rstrip())

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

visited = [False for _ in range(N+1)]
visited[1] = True
ans = [0 for _ in range(N+1)]

iterative_DFS(1)

for a in ans[2:]:
    print(a)