트리의 지름 구하는 공식에 따라 처음은 root인 1 부터 가장 긴 노드 A를 찾고 그 노드 A에서 가장 멀리 있는 노드 B를 찾아, 노드 A와 노드 B 사이의 path 거리를 구했다.
RecursionError 발생 원인
가장 멀리 있는 노드를 찾을 때 dfs를 recursion으로 구현하였는데 조건을 보면 노드의 개수 n(1 ≤ n ≤ 10,000) 이므로 최악의 경우 recursion이 10000번 일어나게 된다. 파이썬에서 recursion 수는 최대 998번으로 제한하고 있으므로 maximum recurion에 의해 RecursionError가 발생한 것이다.
해결 방법
recursion으로 구현한 dfs()를 Iteration(stack)으로 구현해주면 된다.
tree = [collections.defaultdict(int) for i inrange(n+1)] path = [0for i inrange(n+1)] visited = [Falsefor i inrange(n+1)] for _ inrange(n-1): p, c, w = map(int, input().split(' ')) tree[p][c] = w
defdfs(start, before_node, path_length): if visited[start] isTrue: return visited[start] = True
if tree[start][before_node] != 0: path_length += tree[start][before_node]
tree = [collections.defaultdict(int) for i inrange(n+1)] path = [0for i inrange(n+1)] visited = [Falsefor i inrange(n+1)] for _ inrange(n-1): p, c, w = map(int, input().split(' ')) tree[p][c] = w
stack = []
defdfs(start, path_length): stack.append((start, start, path_length)) while stack: curr, before_node, pl = stack.pop() if visited[curr] isFalse: visited[curr] = True if tree[curr][before_node] != 0: pl += tree[curr][before_node]