[アルゴリズム]BOJ 1012有機白菜

[BOJ]2012橄榄球白菜短裙

📍 質問する

次世代農業従事者のハンナは、江原道高寒(カンウォンド・コ寒)地域で有機白菜を栽培することにした.白菜を農薬で栽培しなければ害虫から白菜を守ることが重要なので、ハンナは害虫防止に有効な白菜ミミズを購入することにした.このミミズは白菜の近くに生息し、害虫を捕食することで白菜を保護する.特に、ある白菜に白いミミズが住んでいれば、このミミズは隣の他の白菜に移動することができ、これらの白菜も害虫の保護を受けることができる.1本の白菜の上下左右4方向に異なる白菜がある場合は隣接しています.
ハンナが白菜を植える畑は平らではなく,白菜を植える場所はみなそろっている.白菜が集まっているところに白菜のミミズが1匹あればいいので、隣接する白菜がいくつか分布しているかを調べてみると、全部で何匹必要かがわかります.例えば、白菜畑が以下のように構成されている場合、白菜ミミズは少なくとも5匹必要である.0は白菜を植えていない土地を表し、1は白菜を植えた土地を表す.

📍 入力

入力された第1行は、試験例の個数Tを与える.次の行から、各試験例について、第1行は、キャベツ栽培地の横長M(1≦M≦50)および縦長N(1≦N≦50)およびキャベツ栽培場所の個数K(1≦K≦2500)を与えた.次いでK行はハクサイの位置X(0≦X≦M−1),Y(0≦Y≦N−1)を与える.2つの白菜が同じ位置にある場合はありません.

📍 しゅつりょく

各試験箱について、所望の最小白菜白ミミズ数を出力する.

📍 に答える

ハーモニー

from collections import deque
from sys import stdin

def DFS(x,y):
  dx = [1,-1,0,0]
  dy = [0,0,1,-1]
  D = deque([[x,y]])
  while D:
    [x, y] = D.popleft()
    for i in range(4):
      curX = x + dx[i]
      curY = y + dy[i]
      if  curX < 0 or curX > M-1 or curY < 0 or curY > N-1:
        continue
      if field[curY][curX]:
        D.append([curX,curY])
        field[curY][curX] = 0

T = int(stdin.readline())
result = []
for _ in range(T):
  M, N, K = map(int,stdin.readline().split()) # 가로, 세로, 배추 갯수
  field = [[0 for _ in range(M)] for _ in range(N)]
  for _ in range(K):
    x, y = map(int,stdin.readline().split())
    field[y][x] = 1
  count = 0
  for y in range(N):
    for x in range(M):
      if field[y][x]: # 현재 위치에 배추가 존재한다면
        count += 1 # 지렁이 갯수 + 1
        DFS(x,y) # DFS
  result.append(count)
for c in result:
  print(c)