백준 1012 유기농배추

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

문제

• 인접한 노드(배추)들을 하나의 '뭉치'라고 했을 때, 몇개의 뭉치가 있는지 세는 문제

답안

• 노드들을 한차례 씩 돌면서, 방문하지 않은 배추를 찾는다.
• 배추를 발견하면 cnt +1 계산 후, 인접한 배추들을 모두 방문처리 한다.

import sys
import collections

T = int(sys.stdin.readline())
for _ in range(T):
    m, n, k =  map(int,sys.stdin.readline().split())
    visited =[[False]*m for _ in range(n)]
    graph =[[False]*m for _ in range(n)]
    cnt = 0

    for _ in range(k):
        x,y = map(int,sys.stdin.readline().split())
        graph[y][x] =1 
 
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and visited [i][j] == 0:
                
                #발견하면 cnt+1, 그리고 그 주변을 모두 방문 시킨다.
                cnt +=1
                q= collections.deque()
                q.append((i,j))
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx < n and ny < m and nx >=0 and ny >= 0 and graph[nx][ny] == 1 and visited [nx][ny] == 0:
                            visited[nx][ny] = 1
                            q.append((nx,ny))
    
    print(cnt)