[백준] 1012번 유기농 배추

💡문제접근

• 배추가 심어져 있는 땅 1에 방문하면 상하좌우 네 방향의 위치에 있는 좌표를 0으로 만든 다음 배추흰지렁이의 개체 수를 1만큼 증가시킨다.
• 모든 좌표가 0으로 바뀔때까지 BFS를 반복한다.

💡코드(메모리 : 34144KB, 시간 : 72ms)

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

def BFS(graph, x, y):
    queue = deque()
    # 큐에 시작 좌표를 삽입
    queue.append([x, y])
    # 방문처리
    graph[x][y] = 0
    while queue:
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        x, y = queue.popleft()
        # 상하좌우 네 면
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 만약 좌표 범위 내에 있는 값이 아니라면?
            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue
            # 만약 상하좌우 네 면 중 한 면에 배추가 있다면?
            if graph[nx][ny] == 1:
            	# 해당 좌표를 큐에 삽입
                queue.append([nx, ny])
                # 방문처리
                graph[nx][ny] = 0

T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    farm = [[0] * N for _ in range(M)]
    cnt = 0
    for i in range(K):
        X, Y = map(int, input().split())
        farm[X][Y] = 1

    for a in range(M):
        for b in range(N):
            if farm[a][b] == 1:
                BFS(farm, a, b)
                cnt += 1
    print(cnt)

💡소요시간 : 30m