[Python 3] BJ 1012-유기농 배추

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

1012번: 유기농 배추

dfs를 이용해 배열을 탐색.

파이썬에서 일반적으로 이차원배열을 이용한다면 array[y][x]의 형태로 데이터에 접근해야 한다.

sys.setrecursionlimit(x)는 파이썬에서 재귀의 최대 횟수를 정해 준다. 설정이 되어 있지 않을 경우는 기본 1000회로, 상당히 적은 횟수이기 때문에 일반적으로 \(10^6\)회 정도로 설정해 준다.

import sys
sys.setrecursionlimit(10**6)

delta=[(0, 1), (0, -1), (1, 0), (-1, 0)]

def legal(x, y, M, N):
  if x<0 or y<0 or x>=M or y>=N:
    return 0
  else:
    return 1

def dfs(x, y, check, M, N):
  check[y][x]=0
  for i in range(4):
    dx=x+delta[i][0]
    dy=y+delta[i][1]
    if legal(dx, dy, M, N):
      if check[dy][dx]==1:
        dfs(dx, dy, check, M, N)

T=int(sys.stdin.readline())
for i in range(T):
  M, N, K=map(int, sys.stdin.readline().split())
  check=[[0 for i in range(M)] for i in range(N)]
  count=0
  for i in range(K):
    x, y=map(int, sys.stdin.readline().split())
    check[y][x]=1
  for j in range(N):
    for i in range(M):
      if check[j][i]==1:
        dfs(i, j, check, M, N)
        count+=1
  print(count)