파이썬 재귀 깊이 제한 변경(RecursionError)

RecursionError

BFS/DFS 문제를 풀다보면 RecursionError와 같은 런타임 에러를 마주하는 경우가 있다.

처음엔 코드 상에 문제가 없고 입력값에 맞는 출력값을 제대로 출력했는데도 에러가 떠서 당황했다..

 

RecursionError 해결방법

Python3 기준 최대 재귀 깊이는 1000이다.

그것보다 오버되는 수의 재귀가 호출되는 경우 에러가 발생하는 것이다.

이를 해결하기 위해서 파이썬 기본 재귀 깊이 제한을 임의로 변경하면 되는데

sys 라이브러리의 setrecursionlimit 메소드를 사용하면 된다.

 

백준 1012번 - 유기농 배추 문제

 

처음 제출한 코드 (에러 발생)

- 코드 상에는 문제 없이 제대로 출력되는데 에러가 발생했다.

 

import sys

t = int(sys.stdin.readline())
result = []
cnt = 0
garden = []

def input_a():
  global garden
  global cnt
  m, n, k = map(int, sys.stdin.readline().split())
  garden = [[0] * n for _ in range(m)]
  for i in range(k):
    x, y = map(int, sys.stdin.readline().split())
    garden[x][y] = 1

  for i in range(m):
    for j in range(n):
      if dfs(i, j, garden, m, n) == True:
        cnt += 1

  result.append(cnt)
  cnt = 0  

  

def dfs(x, y, garden, m, n):
  if x <= -1 or x >= m or  y <= -1 or y >= n:
    return False
  if garden[x][y] == 1:
    garden[x][y] = 0
    dfs(x-1, y, garden, m, n)
    dfs(x+1, y, garden, m, n)
    dfs(x, y-1, garden, m, n)
    dfs(x, y+1, garden, m, n)
    return True
  return False
    
      
for j in range(t):
  input_a()

for i in result:
  print(i)
  
  #recursionerror런타임에러

 

해결 코드

 

import sys
# 재귀 깊이 임의 변경
sys.setrecursionlimit(10**4)

t = int(sys.stdin.readline())
result = []
cnt = 0
garden = []

def input_a():
  global garden
  global cnt
  m, n, k = map(int, sys.stdin.readline().split())
  garden = [[0] * n for _ in range(m)]
  for i in range(k):
    x, y = map(int, sys.stdin.readline().split())
    garden[x][y] = 1

  for i in range(m):
    for j in range(n):
      if dfs(i, j, garden, m, n) == True:
        cnt += 1

  result.append(cnt)
  cnt = 0  

  

def dfs(x, y, garden, m, n):
  if x <= -1 or x >= m or  y <= -1 or y >= n:
    return False
  if garden[x][y] == 1:
    garden[x][y] = 0
    dfs(x-1, y, garden, m, n)
    dfs(x+1, y, garden, m, n)
    dfs(x, y-1, garden, m, n)
    dfs(x, y+1, garden, m, n)
    return True
  return False
    
      
for j in range(t):
  input_a()

for i in result:
  print(i)

 

이와 같이 sys.setrecursionlimit(10**4)를 추가해줌으로써 문제가 해결된 것을 확인할 수 있다.

앞으로 DFS/BFS 문제에서 자주 활용되는 재귀함수를 사용할 때 주의해야겠다..!