🔍 Problem

11725 트리의 부모 찾기

---

⚡️ 사용한 알고리즘

DFS

📃 Input&Output

---

📒 해결 과정

dfs에서 다음 좌표에 dfs 시전하기 전에 부모노드 저장해놓는 배열에 부모노드값 저장해놓는다

예를들어
1. 현재 dfs파라미터로 들어온 노드가 1이고 다음 dfs파라미터에 넣을 노드가 2라면
2. parent_info[2] = 1 이런식으로 저장해 놓는다.

---

❗주의점

1. sys.setrecursionlimit(10**6)를 설정해줘야 재귀 호출 스택 오버플로우로 인한 메모리 초과가 발생하지 않는다

---

💻 Code

import sys

sys.setrecursionlimit(10**6)
N=int(sys.stdin.readline())

vst=[False]*(N+1)
graph=[[]for _ in range(N+1)]

parent_info=[0]*(N+1)

for _ in range(N-1):
    n1,n2=map(int,sys.stdin.readline().split())
    graph[n1].append(n2)
    graph[n2].append(n1)
    
def dfs(n):
    vst[n]=True
    
    for i in graph[n]:
        if vst[i]==False:
            parent_info[i]=n
            dfs(i)
    
dfs(1)

for i in range(2,N+1):
    print(parent_info[i])

---

🤔 느낀점

파이썬의 기본 재귀 스택이 최대 1,000이라는 것을 처음 알게 되었고 sys.setrecursionlimit를 10^6까지 해놓고 dfs를 사용하여 코테를 푼다는 정보도 알게되었다.