[BOJ] 1012 유기농 배추

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

문제 요약

• 해충방지를 위해 배추흰지렁이가 몇 마리 필요한지 계산한다.
• 배추가 인접한 지역에는 배추흰지렁이 한 마리면 충분하다.
• 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

접근

처음에는 2차원 리스트의 맨 초기 인덱스인 (0,0)을 재귀적으로 탐색하는 check_ground 함수에 전달하고 이를 해결하면 된다고 생각했다. 하지만 미로탐색과 같은 문제와 달리 이 문제는 탐색해야 하는경로가 이어지지 않기 때문에 인덱스 별로 상,하,좌,우를 확인하고, 인접한 지역에 배추가 있을 경우 다시 해당 인덱스를 기준으로 다시 상,하,좌,우를 탐색하는 방법을 적용해야 했다. (0,0)부터 순차적으로 인접한 배추의 위치를 탐색하고 visited 리스트를 이용해 중복 체크를 방지하는 방법으로 문제를 해결할 수 있었다.

코드

import sys
sys.setrecursionlimit(10**8)

def is_inside_ground(y,x): # x,y 좌표가 유효 범위를 벗어났는지 확인
    if y>=0 and y<r and x>=0 and x<c:
        return True
    return False

def check_ground(y,x): # 방문 체크
    visited[y][x]=True
    for i in control:
        _y=y+i[0]
        _x=x+i[1]
        # 과거에 방문을 안했고, 배추가 있는 경우
        if is_inside_ground(_y,_x) and visited[_y][_x]==False and ground[_y][_x]==1: 
            check_ground(_y,_x)

control=((-1,0),(1,0),(0,-1),(0,1)) # 상,하,좌,우
T=int(input())
for i in range(T):
    c,r,n=map(int,sys.stdin.readline().split())
    ground=[[0]*c for i in range(r)]
    visited=[[False]*c for i in range(r)]
    for j in range(n):
        x,y=map(int,(input().split()))
        ground[y][x]=1
    cnt=0
    for j in range(len(ground)):
        for k in range(len(ground[j])):
            if visited[j][k]==False and ground[j][k]==1:
                check_ground(j,k)
                cnt+=1
    print(cnt)

주의

sys.setrecursionlimit(10**8)

python으로 이 문제를 풀 경우 런타임 오류가 발생한다. python에서 허용하는 재귀횟수를 초과하는 테스트케이스가 존재하는 것 같다. sys.setrecursionlimit(10**8)를 통해 재귀 허용 깊이를 수동으로 늘려주는 코드를 상단에 적어줘야 한다.