백준 알고리즘 1012번

파이썬(BFS사용)

from collections import deque
t = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    q = deque()
    q.append((x,y))
    graph[x][y] = 0


    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<m and graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=0
        
for _ in range(t):
    m,n,k = map(int,input().split())
    graph =[[0]*(m) for _ in range(n)]
    cnt = 0
    for i in range(k):
        x,y = map(int,input().split())
        graph[y][x] = 1
    for a in range(n):
        for b in range(m):
            if graph[a][b]==1:
                bfs(a,b)
                cnt+=1
    print(cnt)