[백준_1012] 유기농배추 python

어제 과음한 관계로,,

오늘은 쉬운 문제,,

# t 입력
t = int(input())
for _ in range(t):
    # m, n, k 입력
    m, n, k = map(int, input().split())

    # mount
    mount = [
        [0] * m
        for _ in range(n)
    ]

    # x, y 입력
    for i in range(k):
        x, y = map(int, input().split())
        # 배추 심어주기
        mount[y][x] = 1
    
    # 함수들
    # in_range(x, y)
    def in_range(x, y):
        return 0 <= x and x < n and 0 <= y and y < m

    # can_go(x, y)
    def can_go(x, y):
        # 범위 내에 있고, 방문한 적 없으며, 배추면 가능
        return in_range(x, y) and not visited[x][y] and mount[x][y]

    # bfs()
    def bfs():
        while q:
            x, y = q.popleft()
            dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
            for dx, dy in zip(dxs, dys):
                # 다음 위치
                nx, ny = x + dx, y + dy
                # 갈 수 있으면
                if can_go(nx, ny):
                    # 방문 처리 해 주고,
                    visited[nx][ny] = 1
                    # 큐에 넣어주기
                    q.append((nx, ny))

    # 설계

    # 큐 사용 준비
    from collections import deque
    q = deque()

    # ans
    ans = 0

    # visited 설계 및 초기화
    visited = [
        [0] * m
        for _ in range(n)
    ]

    # mount 돌면서,
    for i in range(n):
        for j in range(m):
            # 배추를 만나고, 방문한 적 없으면,
            if mount[i][j] and not visited[i][j]:
                # 정답 갯수를 올려주고,
                ans += 1
                # 방문 처리 해주고
                visited[i][j] = 1
                # 큐에 넣어주고
                q.append((i, j))
                # bfs 호출
                bfs()
    
    # 출력
    print(ans)