[백준 11725번] 트리의 부모 찾기

import sys
sys.setrecursionlimit(50000000);

n = int(input())

graph = [[] for _ in range(n+1)]
result = [0]*(n+1)
visited = [False]*(n+1)

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

def dfs(graph,v,visited):
    visited[v] = True
    
    for i in graph[v]:
        if not visited[i]:
            result[i] = v
            dfs(graph,i,visited)

dfs(graph,1,visited)

for i in range(2,n+1):
    print(result[i])

이번 문제는 노드들 간의 연결 관계가 주어진 상황에서 트리의 Root를 1이라고 했을 때, 각 노드의 부모 노드를 구하는 문제이다.

 

문제를 보자마자 각 노드들 간의 관계를 인접 리스트 방식으로 graph(2차원 리스트)에 저장하였고, DFS나 BFS를 사용하여 각 노드의 부모를 쉽게 구할 수 있는 문제이다.

 

여기서 조심해야 할 점은, sys.setrecursionlimit() 로 최대 재귀 깊이를 따로 설정해주지 않으면 런타임 에러(Recursion Error)가 발생할 수 있다는 점이다 !

 

본인은 DFS 방식을 사용하여 풀이하였는데, 오랜만에 DFS를 풀이해보면서 복습할 수 있었던 문제였다 :)