[BOJ 1012] 유기농배추

 

DFS를 이용한 풀이는 아래와 같다.

 

메모리를 보호하려고 백준에서는 재귀함수에 제한을 걸어두었다.

문제 해결에 필요한 정도의 재귀를 허용하기 위해서 아래 함수를 이용했다.

 

sys.setrecursionlimit(5000)

 

import sys

#sys.stdin = open("input.txt", "r")
sys.setrecursionlimit(5000)

T = int(input())

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

def DFS(y, x):
    mapp[y][x] = 0
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if ny < 0 or ny >= N or nx <0 or nx >= M:
            continue
        if mapp[ny][nx] == 0:
            continue
        DFS(ny, nx)
    return


for i in range(T):
    cnt = 0
    M, N, K = map(int, input().split())
    mapp = [[0 for col in range(M)] for row in range(N)]
    for j in range(K):
        x, y = map(int, input().split())
        mapp[y][x] = 1

    #print(mapp)
    for col in range(N):
        for row in range(M):
            if mapp[col][row] == 1:
                DFS(col, row)
                cnt +=1
    print(cnt)