TIL-파이썬의 재귀 깊이 제한 변경

에러를 마주하게 된 경위🤯

최근 BFS/DFS 이론 강의를 다시 듣고 관련 문제들을 풀고 있었다. 에러를 마주하게 된것은 백준 4963번 '섬의 개수' 문제를 풀다가였다. DFS 문제는 어느정도 감이 잡혔다 생각하고 신이 나서 문제를 풀고 제출했는데 웬걸 런타임에러에 나는 것이었다! 자세히 보니 'Recursion Error'로 인해 문제가 발생하는 것을 확인할 수 있었다.

문제가 되었던 코드

if graph[x][y]==1:
        graph[x][y]=0
        for i in range(8):
            dfs(x+dx[i],y+dy[i])
        return True

이 코드는 dfs 함수의 일부분이다. for문을 돌면서 최대 8번의 재귀함수가 호출되게 되는데, 이 부분이 파이썬에서 제한한 재귀 깊이보다 더 많이 호출되어서 위와 같은 에러를 반환하는 것이었다.

해결 방법💡

Python3 기준 최대 재귀 깊이는 1000이라고 한다. 그런데 이 문제의 경우 재귀 깊이는 최대 2500까지 들어갈 수 있어서 문제가 된 셈이다. 결국 임의적으로 파이썬 기본 재귀 깊이 제한을 변경하면 해결되는 것이다. 이를 위해서는 파이썬 sys 라이브러리의 setrecursionlimit 메소드를 사용하면 된다.

문제를 해결하기 위해 삽입한 코드

import sys
sys.setrecursionlimit(2500)

백준 4963번 섬의 개수 문제 바로가기

https://www.acmicpc.net/problem/4963

참고한 자료

• 백준 4963번 섬의 개수 질문들의 답변들
• http://blog.naver.com/PostView.nhn?blogId=luiz4our&logNo=220642911892