[BOJ] 1012번 : 유기농 배추

1. 문제

1012번: 유기농 배추

• 지렁이는 인접 배추로 이동 가능 → 인접한 배추에는 1마리만 있으면 된다.
• 인접 : 상하좌우
• 필요한 지렁이 최소 수
• 0 : 배추 없는 땅
• 1 : 배추

2. 알고리즘

• DFS
• 인접 배추들의 구역 당 지렁이 한 마리 필요
• 인접한 배추들의 구역 수를 구한다.

3. 소스코드

import sys
sys.setrecursionlimit(10000) # 재귀 깊이제한 확장

T = int(input()) # 테스트케이스 수

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    
    if graph[x][y] == 1:
        graph[x][y] = 0
        
        for i in range(4):
            dfs(x + dx[i], y + dy[i])
        
        return True
    return False

for _ in range(T):
    # 가로(열), 세로(행), 배추개수
    m, n, k = map(int, input().split())
    
    graph = [[0] * m for _ in range(n)]
    for _ in range(k):
        col, row = map(int, input().split())
        graph[row][col] = 1 # 배추 표시
        
    ans = 0
    
    for i in range(n):
        for j in range(m):
            if dfs(i, j):
                ans += 1

4. 파이썬

sys.setrecursionlimit(10000)을 하는 이유가 무엇일까?

파이썬은 기본 재귀깊이가 1000으로 매우 얕다. 따라서 dfs를 재귀로 풀 때 recursion error가 자주 발생한다. 이 문제를 해결하기 위해서 sys.setrecursionlimit() 함수를 통해서 재귀 깊이를 확장하는 것이다.