[DFS/BFS/완전탐색] 1012번 - 유기농 배추

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

풀이 시간: 30분 이내

 

이 문제는 DFS, BFS 2가지 방식으로 모두 풀 수 있는 문제다.

최대 재귀한도 깊이 문제로 BFS로 풀이하는 것이 더 좋을 듯 하다.

 

(풀이1) BFS

1) 문제 해결 아이디어

 

 

2) 소스코드

from collections import deque

# 위치벡터(상하좌우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS
def bfs(x, y):
  # 시작 좌표 삽입, 방문처리
  queue = deque()
  queue.append((x, y))
  graph[x][y] = 0

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

      # 좌표 범위 내이면
      if(0 <= nx < n and 0 <= ny < m):
        # 배추이면 삽입, 방문처리
        if(graph[nx][ny] == 1):
          queue.append((nx, ny))
          graph[nx][ny] = 0

t = int(input())  # 테스트 케이스 수

for _ in range(t):
  # 가로, 세로, 배추 개수
  m, n, k = map(int, input().split())
  # 0: 땅, 1: 배추
  graph = [[0] * m for _ in range(n)]
  res = 0  # 지렁이 수
  
  for i in range(k):
    y, x = map(int, input().split())
    graph[x][y] = 1  # 배추 표시

  # 탐색
  for i in range(n):
    for j in range(m):
      # 배추이면
      if graph[i][j] == 1:
        bfs(i, j)
        res += 1  # 지렁이 개수 1증가
  print(res)

 

(풀이1) BFS

1) 문제 해결 아이디어

 

 

2) 소스코드

import sys
sys.setrecursionlimit(10**6)  # 최대 재귀 깊이 설정

t = int(input())  # 테스트 케이스 수
# 위치벡터(상하좌우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# DFS
def dfs(x, y):
  # 현재 좌표 방문 처리
  graph[x][y] = 0

  # 상하좌우 탐색
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    # 좌표 범위 내이면
    if(0 <= nx < n and 0 <= ny < m):
      # 배추이면 재귀 호출
      if(graph[nx][ny] == 1):
        dfs(nx, ny)
  return 0

for _ in range(t):
  # 가로, 세로, 배추 개수
  m, n, k = map(int, input().split())
  # 0: 땅, 1: 배추
  graph = [[0] * m for _ in range(n)]
  res = 0  # 지렁이 수
  
  for i in range(k):
    y, x = map(int, input().split())
    graph[x][y] = 1  # 배추 표시

  # 탐색
  for i in range(n):
    for j in range(m):
      # 배추이면
      if graph[i][j] == 1:
        dfs(i, j)
        res += 1  # 지렁이 개수 1증가
  print(res)

 

첫번째 오류. 런타임 에러: RecursionError

이 에러는 최대 재귀한도 깊이 에러이다.

파이썬에서는 재귀의 한도가 정해져있는데, 

<해결 방법>

1. 재귀 함수를 사용하지 않는 것

DFS대신 BFS로 구현하면 된다.

2. sys.setrecursionlimit() 사용

파이썬이 정한 최대 재귀 깊이를 변경해주는 것이다.

보통 sys.setrecursionlimit(10**6) 정도로 해주면 해결된다.

 

[참고] https://velog.io/@csexpert/python-%EC%B5%9C%EB%8C%80-%EC%9E%AC%EA%B7%80%ED%95%9C%EB%8F%84-%EA%B9%8A%EC%9D%B4-%EC%97%90%EB%9F%ACRecursionError-maximum-recursion-depth-exceeded-in-comparison

[python] 최대 재귀한도 깊이 에러(RecursionError: maximum recursion depth exceeded in comparison)