[python] 백준 1012번 : 유기농 배추 (실버2)

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

런타임 오류가 발생하였다. chat gpt 에게 물어보니 Python의 기본 재귀 한도는 1000으로 설정되어 있으며, 이 한도를 초과하면 RecursionError가 발생한다고 한다.

def move(row,col):
    vegetable[row][col] = False
    if len(vegetable) > row+1 and vegetable[row+1][col] :
        move(row+1,col)
    if row-1 >= 0 and vegetable[row-1][col] :
        move(row-1,col)
    if len(vegetable[0]) > col+1 and vegetable[row][col+1] :
        move(row,col+1)
    if col-1 >= 0 and vegetable[row][col-1]  :
        move(row,col-1)
    return

t = int(input())
for _ in range(t):
    m,n,k = map(int,input().split())
    vegetable = [[False for _ in range(m)] for _ in range(n)]
    
    for _ in range(k):
        col , row = map(int,input().split())
        vegetable[row][col] = True
    count = 0
    for row in range(n):
        for col in range(m):
            if vegetable[row][col] == True:
                move(row,col)
                count += 1
    print(count)

 

해당 오류를 해결하기 위해서는 2가지 방법이 있다.

1. 비재귀적으로 풀기 (추천)

stack을 이용하여 방문하게 될 좌표를 스택에 넣어주면서 더이상 돌아볼곳이 없을떄 까지 진행한다.

def move(row, col):
    stack = [(row, col)]
    while stack:
        row, col = stack.pop()
        if vegetable[row][col]:
            vegetable[row][col] = False
            if row + 1 < len(vegetable) and vegetable[row + 1][col]:
                stack.append((row + 1, col))
            if row - 1 >= 0 and vegetable[row - 1][col]:
                stack.append((row - 1, col))
            if col + 1 < len(vegetable[0]) and vegetable[row][col + 1]:
                stack.append((row, col + 1))
            if col - 1 >= 0 and vegetable[row][col - 1]:
                stack.append((row, col - 1))
    return

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    vegetable = [[False for _ in range(m)] for _ in range(n)]
    
    for _ in range(k):
        col, row = map(int, input().split())
        vegetable[row][col] = True
    
    count = 0
    for row in range(n):
        for col in range(m):
            if vegetable[row][col]:
                move(row, col)
                count += 1
    print(count)

2. 재귀함수 한도를 늘리기 (추천하지는 않음)

import sys
sys.setrecursionlimit(10000)  # 재귀 한도 늘리기

def move(row, col):
    vegetable[row][col] = False
    if len(vegetable) > row + 1 and vegetable[row + 1][col]:
        move(row + 1, col)
    if row - 1 >= 0 and vegetable[row - 1][col]:
        move(row - 1, col)
    if len(vegetable[0]) > col + 1 and vegetable[row][col + 1]:
        move(row, col + 1)
    if col - 1 >= 0 and vegetable[row][col - 1]:
        move(row, col - 1)
    return

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    vegetable = [[False for _ in range(m)] for _ in range(n)]
    
    for _ in range(k):
        col, row = map(int, input().split())
        vegetable[row][col] = True
    
    count = 0
    for row in range(n):
        for col in range(m):
            if vegetable[row][col]:
                move(row, col)
                count += 1
    print(count)