[백준] 유기농 배추.py

from collections import deque
import sys
t = int(sys.stdin.readline())
dirs = [(1,0), (-1,0), (0,1), (0,-1)]

def bfs(start, maps):
    queue = deque()
    queue.append(start)
    while queue:
        y, x = queue.popleft()
        # 해당 위치에는 배추가 존재한다고 이미 개수를 셌으므로 배추 위치를 0으로 바꿔준다
        maps[y][x] = 0
        for move in dirs:
            new_y, new_x = y + move[0], x + move[1]
            # 인접한 곳에도 배추가 있을 경우
            if 0 <= new_y < height and 0 <= new_x < width and maps[new_y][new_x]:
                queue.append((new_y, new_x))
                maps[new_y][new_x] = 0

    # 배추가 모여 있는 그룹을 하나 찾았으므로
    return 1
for _ in range(t):
    width, height, n = map(int, sys.stdin.readline().split())
    maps = [[0 for _ in range(width)] for _ in range(height)]
    for _ in range(n):
        x, y = map(int, sys.stdin.readline().split())
        maps[y][x] = 1
    count = 0
    for y in range(height):
        for x in range(width):
            # 배추 위치가 1이면 bfs 함수를 실행해 그룹을 찾는다.
            if maps[y][x] == 1:
                count += bfs((y,x), maps)
    print(count)