[백준 1012번] 유기농 배추 - python

문제 링크

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

1012번: 유기농 배추

풀이

- bfs로 풀이

from collections import deque 

test = int(input())

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

def bfs(a,b):
  # 0으로 지나간 곳임을 표시 
  graph[a][b] = 0 
  # 큐에 위치 삽입 
  q = deque()
  q.append((a,b))

  while q:
    x,y = q.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      # 범위에 해당하고 배추가 심어져 있는 곳이면 
      if 0<= nx < n and 0 <= ny < m and graph[nx][ny] == 1 :
        # 0으로 표시 
        graph[nx][ny] = 0
        q.append((nx,ny))

for _ in range(test):
  n, m, k = map(int,input().split())
  
  # 배추 밭 
  graph =[[0] * m for _ in range(n)]
  
  # 배추의 위치 표시 
  for _ in range(k):
    a, b = map(int,input().split())
    graph[a][b] = 1 
  
  # 흰지렁이 수 
  cnt = 0 
  for i in range(n):
    for j in range(m):
      # 배추가 심어져 있는 곳이면 bfs 실행 후 cnt + 1 
      if graph[i][j] == 1:
        bfs(i,j)
        cnt += 1 

  print(cnt)