[백준] 1012. 유기농 배추 - python3

1012. 유기농 배추

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

1012번: 유기농 배추

 

 

내 풀이 - 성공

from sys import stdin
import sys

sys.setrecursionlimit(10**6)

T = int(stdin.readline())

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)

for _ in range(T):
    M, N, K = map(int, stdin.readline().split())
    answer = 0
    field = []
    for i in range(N):
        field.append([0]*M)

    for k in range(K):
        X, Y = map(int, stdin.readline().split())
        field[Y][X] = 1
    
    for i in range(N):
        for j in range(M):
            if field[i][j]:
                answer += 1
                func(field, i, j)
    
    print(answer)

 

field 라는 2차원 배열을 만들어주고 배추는 1, 아닌 부분은 0 으로 채워줬다.

다시 하나씩 보면서 1 을 만나면 재귀를 이용해 1 과 연결된 배추들을 모두 0 으로 바꿔줬다.

그럴 때마다 answer 도 + 1

 

참고로 파이썬의 기본 재귀 깊이는 1000 이라서 매우 얕기 때문에

sys.setrecursionlimit 으로 늘려줘야 정상적으로 돌아간다.

 

없으면 런타임 에러 (RecursionError) 뜸