DFS 문제를 통해 여러 시행착오를 거칠 필요가 있다고 생각했던 나는 한 문제를 더 찾아서 풀기 시작했고,
재귀 함수를 이용했기에 발생했던 런타임 에러가 발생했다
해결법도 찾았고, 그 방법까지 해서 이번 글에 포스팅하려고 한다
문제
문제 분석
이 문제는 DFS를 이용하여 블록단위 탐색을 이용하면 되지만 몇 가지 유의사항이 존재한다
그래프 형태로 존재하는 것이 아닌 좌표단위로 존재하는 것 -> 가상의 그래프 맵을 만든다
배추밭이 굉장히 넓어졌을 때 재귀를 이용할 경우 깊이의 한계에 막히는 것 -> sys를 import해서 이를 방지한다
코드 작성
# Python 자체의 최대 재귀 깊이가 달라질 수 있기에 1000회가 넘을 것으로 예상되면
# sys.setrecursionlimit(10**6)으로 10억회를 설정해서 recursion error을 피하도록 하자
import sys
sys.setrecursionlimit(10**6)
# 테스트 케이스 개수
T = int(input())
# 재귀를 이용한 상하좌우 DFS 블록탐색 함수
def dfs(xpos, ypos):
if xpos >= N or xpos <= -1 or ypos >= M or ypos <= -1:
return False
if d[xpos][ypos] == 1:
d[xpos][ypos] = 0
dfs(xpos + 1, ypos)
dfs(xpos - 1, ypos)
dfs(xpos, ypos + 1)
dfs(xpos, ypos - 1)
return True
return False
# 테스트 케이스 만큼 반복
for _ in range(T):
M, N, K = map(int, input().split())
d = [[0] * M for _ in range(N)]
for i in range(K):
# 여기서 주의할 점: y, x의 형태로 심어지므로 좌표값을 변경할 때 주의하자
x, y = map(int, input().split())
d[y][x] = 1
result = 0
# 2중 반복문으로 블록 개수 탐색
for i in range(N):
for j in range(M):
if dfs(i, j) == True:
result += 1
print(result)
RuntimeError : recursion Error 이 발생하는 이유는 Python 자체에서 재귀함수의 재귀 깊이를 막아놓았기 때문인데,
Python에서는 10억회를 무한에 가까운 수로 지정하고 있기에
sys를 불러와서 setrecursionlimit을 10억회로 지정해둔다면 이 에러가 해결된다