[백준/Python] 트리의 부모 찾기

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

 

---

각 노드마다 연결되어있는 노드를 저장하는 이차원 리스트를 만든다

각 노드가 방문 여부를 저장하는 리스트를 만든다

부모 노드를 저장하기 위한 parents라는 리스트를 만든다

 

-> DFS

 

import sys
input= sys.stdin.readline


def dfs(node):
    st = [node]
    
    while st:
        v = st.pop()
        for n in graph[v]:
            if visited[n] == False:
                parents[n] = v
                visited[n] = True
                st.append(n)

n = int(input())

parents = [i for i in range(n+1)]

graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)
    
visited = [False] * (n+1)

dfs(1)
for i in parents[2:]:
    print(i)

 

재귀로 풀면 RecursionError가 나기 때문에 while문으로 만들어야 한다!