[백준] 11725: 트리의 부모 찾기 python 구현 / DFS

문제

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

사실 처음에는 문제가 잘 이해가 가지 않아 tree 구조를 손으로 그려보니 이해가 편했다. 2번 노드부터 순서대로 부모노드를 출력하는 것

풀이

DFS로 구현하였다.

vst에 1로 방문처리를 하는게 아니라 부모노드(current node)를 표시하며 방문 처리를 진행했다.

이번 문제에서도 재귀의 깊이를 확장해주었어야 했다.

또한 같은 코드로 pypy3으로 제출하였을 때 메모리 에러가 나는 것을 보면,, pyhon3보다 메모리 관리는 부족한가보다

 

 CODE

import sys
sys.setrecursionlimit(10**7) 

n = int(input())
adj_list = [[] for _ in range(n+1)]
for _ in range(n-1):
    n1, n2 = map(int, sys.stdin.readline().split())
    adj_list[n1].append(n2)
    adj_list[n2].append(n1)

def dfs(c_node):
    # 존재하는 경우 for loop 돌기
    for i in adj_list[c_node]:
        # 방문했다면 continue
        if vst[i]: continue
        vst[i] = c_node
        dfs(i)

vst = [0] * (n+1)
vst[1] = 1
dfs(1) # root node
for i in vst[2:]:
    print(i)