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

초고

import sys
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def dfs(x,y): #상하좌우 확인
   visited[x][y] = True
   for i in range(4):
       nx, ny = x+ dx[i], y+dy[i]
       if nx<0 or nx >=m or ny<0 or ny >=n:
            continue #어차피 안쪽에 있는애가 건들여서 도는게 더 좋으니
       if graph[nx][ny] and not visited[nx][ny]:
           dfs(nx,ny)


t = int(sys.stdin.readline())
for i in range(t):
    m,n,k = map(int, sys.stdin.readline().split(" "))
    visited = [[False]*n for _ in range(m)]
    graph = [[0] * n for _ in range(m)]
    cnt = 0
    for i in range(k):
        x,y = map(int,sys.stdin.readline().split(" "))
        graph[x][y] = 1
    cnt =0
    for i in range(m):
        for j in range(n):
            if graph[i][j] and not visited[i][j]:
                dfs(i,j)
                cnt+=1
    print(cnt)

런타임 에러 발생

• RecursionError
  https://help.acmicpc.net/judge/rte/RecursionError

RecursionError는 재귀와 관련된 에러입니다. 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때입니다.

Python이 정한 최대 재귀 깊이는 sys.getrecursionlimit()을 이용해 확인할 수 있습니다. BOJ의 채점 서버에서 이 값은 1,000으로 되어 있습니다.

해결방법

• 첫 번째는 재귀 함수를 사용하지 않는 것입니다. => DFS를 이용했다면 BFS로, 다이나믹 프로그래밍을 재귀로 구현했다면 반복문으로 구현하는 것 처럼 재귀를 사용하지 않게 구현하는 방법으로 해결

• 두 번째는 sys.setrecursionlimit()을 사용하는 것입니다.
  이 함수를 사용하면, Python이 정한 최대 재귀 갚이를 변경할 수 있습니다. => 그러나 제한이 너무 높게 설정되면 스택 오버플로가 발생할 수 있으므로 일반적으로 권장되지 않습니다.

2트

스택을 사용하여 반복적으로 DFS를 구현

import sys
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def dfs(x,y): #상하좌우 확인
   stack = [(x,y)] # 방문할 노드를 추적
   while stack: #스택이 비워질때까지
       x,y = stack.pop()
       if not visited[x][y]:
          visited[x][y] = True
       for i in range(4):
           nx, ny = x+ dx[i], y+dy[i]
           if nx<0 or nx >=m or ny<0 or ny >=n:
                continue #어차피 안쪽에 있는애가 건들여서 도는게 더 좋으니
           if graph[nx][ny] and not visited[nx][ny]:
               stack.append((nx,ny))# 방문안한애들 push


t = int(sys.stdin.readline())
for i in range(t):
    m,n,k = map(int, sys.stdin.readline().split(" "))
    visited = [[False]*n for _ in range(m)]
    graph = [[0] * n for _ in range(m)]
    cnt = 0
    for i in range(k):
        x,y = map(int,sys.stdin.readline().split(" "))
        graph[x][y] = 1
    cnt =0
    for i in range(m):
        for j in range(n):
            if graph[i][j] and not visited[i][j]:
                dfs(i,j)
                cnt+=1
    print(cnt)