[백준] 1012 - 유기농 배추(파이썬, Python)

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

1012번: 유기농 배추

 

 

import sys

def dfs(pos_r, pos_c):
    stack = [(pos_r, pos_c)]
    matrix[pos_r][pos_c] = 0

    dr = [0, 1, 0, -1]
    dc = [-1, 0, 1, 0]

    while stack:
        pos = stack.pop()

        for k in range(4):
            cr = pos[0] + dr[k]
            cc = pos[1] + dc[k]

            if(0 <= cr < N and 0 <= cc < M and matrix[cr][cc] == 1):
                stack.append((cr, cc))
                matrix[cr][cc] = 0



T = int(sys.stdin.readline().rstrip())

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().rstrip().split())

    matrix = [[0]*M for _ in range(N)]
    answer = 0

    for _ in range(K):
        pos_c, pos_r = map(int, sys.stdin.readline().rstrip().split())
        matrix[pos_r][pos_c] = 1

    for i in range(N):
        for j in range(M):
            if(matrix[i][j] == 1):
                answer += 1
                dfs(i, j)

    print(answer)