[BOJ] #1012：有机白菜（Python）

import sys
from collections import deque
 
sys.setrecursionlimit(10000)  # DFS 사용 시 재귀 제한 증가 (예방 차원)
 
T = int(sys.stdin.readline())  # 테스트 케이스 수
dx = [0, 0, 1, -1]  # 좌우
dy = [1, -1, 0, 0]  # 상하
 
for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())  # 가로(M), 세로(N), 배추 위치 수(K)
    ground = [[0] * M for _ in range(N)]  # 배추밭 초기화 (세로 x 가로)
    visited = [[False] * M for _ in range(N)]  # 방문 체크 배열
 
    for _ in range(K):  # 배추 위치 표시
        x, y = map(int, sys.stdin.readline().split())
        ground[y][x] = 1
 
    # BFS로 연결된 배추 그룹 탐색
    def bfs(y, x):
        queue = deque()
        queue.append((y, x))
        visited[y][x] = True
        while queue:
            cy, cx = queue.popleft()
            for d in range(4):
                ny, nx = cy + dy[d], cx + dx[d]
                if 0 <= ny < N and 0 <= nx < M:
                    if not visited[ny][nx] and ground[ny][nx] == 1:
                        visited[ny][nx] = True
                        queue.append((ny, nx))
 
    count = 0  # 지렁이 수
    for i in range(N):
        for j in range(M):
            if not visited[i][j] and ground[i][j] == 1:
                bfs(i, j)
                count += 1  # 새로운 연결 그룹 발견 시 증가
 
    print(count)

1
5 1 5
0 0
1 0
2 0
3 0
4 0

1
3 3 3
0 0
1 1
2 2

1
3 3 2
0 0
2 2