[백준 런타임 에러(RecursionError)] 파이썬 최대 재귀 깊이 초과

파이썬은 기본적으로 최대 재귀 깊이가 1000으로 설정되어 있어 dfs와 같은 문제를 해결하다 보면 최대 깊이를 초과하는 경우가 있다.  이 때 아래와 같이 최대 깊이를 바꿔주면 문제가 해결된다 하지만 너무 높게만 설정해도 메모리 초과가 발생할 수 있다. 

import sys
sys.setrecursionlimit(10 ** 6)

 

 

따라서 최대 재귀 깊이는 그래프 탐색의 경우 노드의 개수를 넘을 수 없다. 

ex) 노드의 개수가 5의 경우

node : 1, 2, 3, 4, 5 

1 -> 2 : 1번 노드와 2번 노드가 연결되어 있음

2 -> 3 : 2번 노드가 3번 노드와 연결되어 있음

3 -> 4 : 3번 노드가 4번 노드와 연결되어 있음

4 -> 5 : 4번 노드와 5번 노드가 연결되어 있음

 

위와 같은 경우 1번 노드부터 탐색하면

1 -> 2 -> 3 -> 4 -> 5

위와 같이 최대 노드 깊이는 5를 넘을 수 없다. 따라서 메모리초과와 런타임 에러를 피하기 위해서는 아래와 같이 최대노드 수로 정해주면 된다. 하지만 약간 불안할 수 있으니 +1를 해주자..!!

import sys
sys.setrecursionlimit(최대노드수+1)