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

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

1012번: 유기농 배추

<BFS>

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

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

def bfs(x,y):
  queue = deque()
  queue.append((x,y))
  matrix[x][y] = 0

  while queue:
    a, b = queue.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]

      if nx < 0 or ny < 0 or nx >= h or ny >= w:
        continue
      if matrix[nx][ny] == 0:
        continue
      if matrix[nx][ny] == 1:
        matrix[nx][ny] = 0
        queue.append((nx,ny))

case = int(input())

# 행렬 만들기
for _ in range(case):
  w, h, k = map(int, read().split())
  matrix = [[0] * w for _ in range(h)]
  cnt = 0

  for _ in range(k):
    x, y = map(int, read().split())
    # 인덱스 변수 순서 고려
    matrix[y][x] = 1

  for i in range(h):
    for j in range(w):
      if matrix[i][j] == 1:
        bfs(i,j)
        cnt += 1
  
  print(cnt)

<DFS>

import sys
sys.setrecursionlimit(10000)
read = sys.stdin.readline

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

def dfs(x,y):
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if nx < 0 or ny < 0 or nx >= h or ny >= w:
      continue
    if matrix[nx][ny] == 0:
      continue
    if matrix[nx][ny] == 1:
      matrix[nx][ny] = 0
      dfs(nx,ny)

case = int(input())

# 행렬 만들기
for _ in range(case):
  w, h, k = map(int, read().split())
  matrix = [[0] * w for _ in range(h)]
  cnt = 0

  for _ in range(k):
    x, y = map(int, read().split())
    # 인덱스 변수 순서 고려
    matrix[y][x] = 1

  for i in range(h):
    for j in range(w):
      if matrix[i][j] == 1:
        dfs(i,j)
        cnt += 1
  
  print(cnt)

import sys
sys.setrecursionlimit(10000)

위 코드는 재귀의 한도를 풀어주는 함수이다.

만약 재귀를 사용해서 풀어야 하는 문제라면, 해당 코드는 선택이 아닌 필수다.

파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이므로 재귀로 문제를 풀 경우 드물지 않게 이 제한에 걸리게 된다. 재귀함수를 사용한다면 꼭 써주어야 한다!

 

출처 url: https://velog.io/@falling_star3/%EB%B0%B1%EC%A4%80Python-1012%EB%B2%88-%EC%9C%A0%EA%B8%B0%EB%86%8D-%EB%B0%B0%EC%B6%94