[파이썬] 11725번 '트리의 부모' 문제 풀이

[파이썬] 11725번 '트리의 부모' 문제 풀이

트리를 탐색하며 각 노드에 대해 부모 노드가 무엇인지 묻는 문제입니다.

트리의 루트를 1이라고 정했기 때문에 출력시 2번에 해당되는 노드부터 출력합니다.

예제

위의 예제를 이미지로 나타내면 다음과 같습니다.

2번 노드에 대한 부모 노드는 4

3번 노드에 대한 부모 노드는 6

4번 노드에 대한 부모 노드는 1

5번 노드에 대한 부모 노드는 3

6번 노드에 대한 부모 노드는 1

7번 노드에 대한 부모 노드는 4

방문하는 과정에서 방문하지 않은 노드가 있다면 현재 확인 중인 노드가 부모 노드가 됩니다.

dfs를 이용한 풀이

※노드의 개수가 최대 100,000개이기 때문에 최대 재귀 깊이가 파이썬에서 기본 지원하는 최대 재귀 깊이 1000을 넘기게 됩니다.

따라서 sys모듈의 setrecursionlimit함수를 사용하여 최대 재귀 깊이를 늘려줍니다.

import sys sys.setrecursionlimit(10**9) def dfs(V): visited[V]=True for i in graph[V]: if not visited[i]: answer[i]=V dfs(i) N=int(input()) graph=[[] for _ in range(N+1)] visited=[False for _ in range(N+1)] answer=[1 for _ in range(N+1)] for i in range(N-1): A,B=map(int,input().split()) graph[A].append(B) graph[B].append(A) #↓방문 순서를 확인할 필요없고 부모 노드만 확인하면 되기때문에 생략해도 상관x for i in graph: i.sort() dfs(1) for i in range(2,len(answer)): print(answer[i])

문제 출처: https://www.acmicpc.net/problem/11725

from http://lbdiaryl.tistory.com/191 by ccl(A) rewrite - 2021-10-26 13:00:24