이 문제는 전형적인 dfs 문제로, 풀이 방법은 간단하였다. 그러나 답은 제대로 출력되었지만 solved.ac에 제출하였을 때 계속해서 런타임에러(RecursionError)가 발생하였다. 반복문을 탈출하지 못하여 발생하는 오류라고 생각하였으나, 아무리 로직을 다시 들여다보아도 틀린 부분을 찾지 못했다. 알고보니 이는 파이썬의 재귀 깊이 제한 때문에 발생하는 문제로, 내가 작성한 로직에는 아무런 문제가 없었다.
파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이다. 이는 sys 모듈의 getrecursionlimit() 함수를 사용해서 확인할 수 있다. 따라서 재귀로 문제를 풀 경우 드물지 않게 이 제한에 걸리게 되는데, 문제는 실제 코딩테스트 환경에서는 에러 메시지를 볼 수 없다는 것이다. #11724번 문제의 노드의 개수는 최대 1000개이기 때문에 이러한 재귀 깊이 제한 때문에 계속해서 RecursionError가 발생했던 것이다. 재귀를 활용한 문제를 풀 때는 상단에 꼭 다음 코드를 작성하는 것을 습관화하여 이러한 에러를 방지할 수 있도록 해야겠다.
import sys
sys.setrecursionlimit(10 ** 6)위 코드는 재귀의 최대 깊이를 10**6으로 변경해준다.
🚨다만, PyPy에서는 sys.setrecursionlimit()으로 임의로 재귀의 최대 깊이를 설정할 수 없다.
나는 sys.setrecursionlimit()을 설정했지만, 입력 방식을 input()으로 작성한 채 코드를 다시 제출하여 시간 초과가 발생하였다. 몇 시간 전에 작성한 포스트에서 sys.stdin.readline()으로 입력받는 습관을 들여야겠다고 다짐해놓고 이런 실수를 하다니!
👉 input()이 sys.stdin.readline()보다 느린 이유 보러가기
이번 포스트의 핵심은 다음과 같다.
- 파이썬으로 재귀를 이용한 문제를 풀 때는 재귀 깊이 제한 늘리기
import sys
sys.setrecursionlimit(10 ** 6)- 시간초과 방지를 위해 sys.stdin.readline()으로 입력받기
참고문헌
https://fuzzysound.github.io/sys-setrecursionlimit
https://kingnamji.tistory.com/39
