[알고리즘] 백준 1012 유기농 배추 / python

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

1012번: 유기농 배추

 

재귀가 깊어서 런타임에러가 발생할 수 있으니 재귀깊이를 설정해주는 코드를 추가해줬다

배추가 있는곳에서 dfs함수를 호출해 상하좌우 배추가 있는지 검사해주고 있다면 -1로 바꾼다

인접한 범위에서 검사할 배추가 없다면 나오게 되고, 카운트+1해준다

떨어진 곳의 배추에서 다시 dfs함수를 부르고.. 반복한다

 

import sys
sys.setrecursionlimit(10000)

def dfs(X, Y):
    global MAP, M, N
    dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
    MAP[X][Y] = -1
    for i in range(4):
        XX, YY = X + dx[i], Y + dy[i]
        if XX < 0 or XX == M or YY < 0 or YY == N:
            continue
        if MAP[XX][YY] == 1:
            MAP[XX][YY] = -1
            dfs(XX, YY)

T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    MAP = [[0]*N for _ in range(M)]
    count = 0
    for _ in range(K):   
        X, Y = map(int, input().split())
        MAP[X][Y] = 1
    for i in range(M):
        for j in range(N):
            if MAP[i][j] > 0:
                dfs(i, j)
                count += 1
    print(count)