1012번: 유기농배추 (그래프, BFS, DFS) - Fastcampus

www.acmicpc.net/problem/1012

1012번: 유기농 배추

from collections import deque


def bfs(sx, sy):
    qu = deque([(sx, sy)])

    while qu:
        x, y = qu.popleft()
        if not visited[x][y]:
            visited[x][y] = 1
            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < N and 0 <= ny < M and MP[nx][ny]:
                    qu.append((nx, ny))


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    MP = [[0] * M for _ in range(N)]
    for _ in range(K):
        y, x = map(int, input().split())
        MP[x][y] = 1

    visited = [[0] * M for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(M):
            if MP[i][j] and not visited[i][j]:   # 연결된 배추는 카운트에서 제외
                cnt += 1
                bfs(i, j)  # 연결된 배추 찾기
    print(cnt)