[백준] 1021번: 유기농 배추

BACKJOON>1021번: 유기농 배추

📘 문제풀이

from collections import deque
import sys
sys.setrecursionlimit(10000)

t = int(sys.stdin.readline())

def bfs(cx, cy, graph, visited):
    queue.append((cx, cy))
    visited[cx][cy] = True    
    
    while queue:
        px, py = queue.popleft()
        
        for i in range(4):
            nx = px + dx[i]
            ny = py + dy[i]            
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if visited[nx][ny] == False and case[nx][ny] != 0:
                queue.append((nx, ny))
                visited[nx][ny] = True
                case[nx][ny] = case[px][py] + 1

for i in range(t):
    m, n, c = map(int, sys.stdin.readline().split())
    case = [[0] * m for _ in range(n)]
    for _ in range(c):
        y, x = map(int, sys.stdin.readline().split())
        case[x][y] = 1
    visited = [[False] * m for _ in range(n)]

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    queue = deque()

    b = 0
    for i in range(n):
        for j in range(m):
            if case[i][j] == 1:
                cx = i
                cy  = j
                bfs(cx, cy, case, visited)
                b += 1
    print(b)