[백준] 1012번 유기농 배추 (Python 파이썬)

 

배추밭과 심어진 배추 위치 정보를 배열에 저장한 뒤, 배열을 BFS로 탐색하면 된다.

 

BFS나 DFS로 탐색하면 한 위치에서 출발해서 갈 수 있는 모든 점을 탐색할 수 있기 때문에 인접한 배추를 모두 한 번에 구할 수 있다. 

 

다른 문제에서는 이미 탐색한 지점을 구분하기 위해 visited라는 배열을 선언하기도 하지만, 여기서는 이를 구분하기 위해 이미 탐색한 배열 값을 1에서 0으로 바꿔 주었다. 

 

import sys
from collections import deque
input = sys.stdin.readline

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

def bfs(start_x, start_y):
    queue = deque([[start_x, start_y]])
    arr[start_x][start_y] = 0
    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue
            if arr[nx][ny] == 1:
                queue.append([nx, ny])
                arr[nx][ny] = 0


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    arr = [[0] * N for _ in range(M)]
    for _ in range(K):
        a, b = map(int, input().split())
        arr[a][b] = 1
    
    cnt = 0
    for i in range(M):
        for j in range(N):
            if arr[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)