본문 바로가기
알고리즘/백준

[백준 - SILVER 2] 1012. 유기농 배추 - Python3

by jsh5408 2021. 9. 25.

1012. 유기농 배추

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

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

 

내 풀이 - 성공

import sys
sys.setrecursionlimit(10**6)

def func(field, i, j):
    field[i][j] = 0

    if i > 0 and field[i-1][j]:
        func(field, i-1, j)
    if j > 0 and field[i][j-1]:
        func(field, i, j-1)
    if i < len(field)-1 and field[i+1][j]:
        func(field, i+1, j)
    if j < len(field[0])-1 and field[i][j+1]:
        func(field, i, j+1)

ans = []
T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())

    field = []
    for _ in range(N):
        field.append([0]*M)

    for _ in range(K):
        x, y = map(int, input().split())
        field[y][x] = 1

    a = 0

    for i in range(N):
        for j in range(M):
            if field[i][j]:
                a += 1
                func(field, i, j)
    ans.append(a)

for a in ans:
    print(a)

 

field 값이 1 이면 재귀 돌려서 인접한 모든 배추들을 0 으로 바꿔주기


그때마다 a + 1 해주며 세준 지렁이를 ans 에 저장해서 한번에 출력

 

Python 재귀 깊이
import sys
sys.setrecursionlimit(10**6)​

파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이므로
setrecursionlimit => Python이 정한 최대 재귀 깊이를 변경해줘야 함

 

참고
https://help.acmicpc.net/judge/rte/RecursionError

 

댓글