[Graph] 유기농 배추

from collections import deque

direction = {0: (0, 1), 1: (0, -1), 2: (1, 0), 3: (-1, 0)}


def BFS(cabbage, a, b):
    q = deque()
    q.append((a, b))
    cabbage[a][b] = 0

    while q:
        x, y = q.popleft()
        for i in range(4):
            x2, y2 = x + direction[i][0], y + direction[i][1]
            if 0 <= x2 < N and 0 <= y2 < M and cabbage[x2][y2] == 1:
                q.append((x2, y2))
                cabbage[x2][y2] = 0
                
    return 1

T = int(input())

for t in range(T):
    M, N, K = map(int, input().split())
    cabbage = [[0 for m in range(M)] for n in range(N)]

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

    count = [BFS(cabbage, a, b) for b in range(M) for a in range(N) if cabbage[a][b] == 1]

    print(len(count))

주어진 배추의 위치는 2차원 배열
인접해있는 배추 집합의 최소 개수를 구하는 문제 -> BFS 활용
전에 풀었던 문제를 참고하여 위쪽 아래쪽 오른쪽 왼쪽 방향으로 이동하는 경우를 계산
행과 열 인덱스와 범위가 헷갈렸어서 다음부터는 이 부분 유의