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 활용
전에 풀었던 문제를 참고하여 위쪽 아래쪽 오른쪽 왼쪽 방향으로 이동하는 경우를 계산
행과 열 인덱스와 범위가 헷갈렸어서 다음부터는 이 부분 유의