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

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

1012번: 유기농 배추

문제를 보자마자 BFS써야겠다라는 생각뿐.

단순하게 농장을 2차원 배열로 받아서 배추가 있는 부분만 1로 표시한다.

농장 전체를 훑으면서 배추가 있고 아직 탐색을 안한 부분이면 BFS를 돌리면 된다. 

BFS가 끝나면 그 부분에 배추흰지렁이가 필요하므로 count += 1을 해주면 된다.

그렇게 농장 전체를 훑으면 인접한 부분당 배추흰지렁이가 있는 것으로 탐색되므로 농장을 탐색하면서 BFS를 한 횟수가

결국 배추흰지렁이의 마릿수가 된다.

코드는 다음과 같다.

 

import sys
from collections import deque
input = sys.stdin.readline
T = int(input())

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

def BFS(x,y):
  
  queue.append((x,y))
  visited[x][y] = True
  while queue:
    (a, b) = queue.popleft()
    for i in range(4):
      temp_a = a + dx[i]
      temp_b = b + dy[i]
      if temp_a >= 0 and temp_b >= 0 and temp_a <= M-1 and temp_b <= N-1:
        if farm[temp_a][temp_b] == 1 and not visited[temp_a][temp_b]:
          visited[temp_a][temp_b] = True
          queue.append((temp_a, temp_b))

for _ in range(T):
  M, N, pos = map(int,input().split())
  queue = deque([])
  visited = [[False for _ in range(N)] for _ in range(M)]
  farm = [[0 for _ in range(N)] for _ in range(M)]
  count = 0
  for _ in range(pos):
    x, y = map(int,input().split())
    farm[x][y] = 1
  
  for i in range(M):
    for j in range(N):
      if farm[i][j] == 1 and not visited[i][j]:
        BFS(i,j)
        count += 1
  print(count)

 

 

글이나 코드에 대한 조언 모두 환영합니다.