[백준] 1012번 - 유기농 배추 (파이썬 Recursion Error 해결)

 

백준 1012번 문제 파이썬

 

 

 

"💡 문제 해결 아이디어"

 

유기농 배추 문제는 완전 탐색을 통해 해결해야하는 문제이다.

 

본인은 dfs를 통해 해결하였다.

 

0,0부터 n-1,m-1 까지 모두 돌며 값이 1인 곳(배추가 심어진 곳)을 찾는다.

 

지렁이는 상하좌우로 퍼져나갈 수 있기 때문에, 배추가 심어진 곳을 발견하면 그 구간에서 dfs를 돌려 인접해있는 1들을 모두 0으로 변경하고 1을 카운트한다.

 

이렇게 하면 인접해 있는 배추 그룹의 갯수를 전부 파악할 수 있어 지렁이가 총 몇 마리 필요한 지 구할 수 있다.

 

 

"❗ 런타임 에러(RecursionError) 해결"

 

RecursionError

dfs를 사용하면 편리하지만 벡준에서 지정한 기본 재귀 depth 때문에 런타임에러가 발생한다.

 

때문에 sys.setrecursionlimit()을 1000000정도 주게되면 문제가 해결된다.

 

 

 

코드

import sys
sys.setrecursionlimit(1000000)

def dfs(x, y, graph):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    if graph[x][y] == 1:
        graph[x][y] = 0
        dfs(x+1, y, graph)
        dfs(x-1, y, graph)
        dfs(x, y+1, graph)
        dfs(x, y-1, graph)
        return True
    return False


t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    graph = [[0 for _ in range(m)] for _ in range(n)]
    for _ in range(k):
        y, x = map(int, input().split())
        graph[x][y] = 1

    result = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                if dfs(i, j, graph) == True:
                    result += 1
    print(result)