백준 1012번 : 유기농 배추(python)

 

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

t = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def dfs(x,y):
    q = [(x,y)]
    while q:
        x,y = q.pop()
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m and data[nx][ny]==1:
                data[nx][ny] = 0
                q.append((nx,ny))

for _ in range(t):
    m,n,k = map(int,input().split())
    data = [[0]*m for _ in range(n)]
    for _ in range(k):
        a,b = map(int,input().split())
        data[b][a] = 1
    cnt = 0
    for x in range(n):
        for y in range(m):
            if data[x][y] == 1:
                cnt += 1
                dfs(x,y)
    print(cnt)