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

출처 : 백준, https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

DFS! DFS!

 

 

첫 번째 풀이 : RecursionError

 

def DFS(current, matrix):
  dx = [1, -1, 0, 0]
  dy = [0, 0, 1, -1]
  x, y = current

  if matrix[x][y] <= 0:
    return 0
  else:
    matrix[x][y] = -1
    
    for i in range(4):
      if 0 <= x + dx[i] < len(matrix) and 0 <= y + dy[i] < len(matrix[0]):
        DFS((x+dx[i], y+dy[i]), matrix)

    return 1
  
if __name__ == '__main__':
  T = int(input())
  
  for i in range(T):
    row, col, count = map(int, input().split())
    cabbage = [list(map(int, input().split())) for _ in range(count)]
    matrix = [[0] * col for _ in range(row)]
    ans = 0

    for node in cabbage:
      x, y = node
      matrix[x][y] = 1

    for node in cabbage:
      ans += DFS(node, matrix)

    print(ans)

 

재귀 한계 에러남.

 

 

두 번째 풀이 : 성공

 

import sys
sys.setrecursionlimit(10**6)

def DFS(current, matrix):
  dx = [1, -1, 0, 0]
  dy = [0, 0, 1, -1]
  x, y = current

  if matrix[x][y] <= 0:
    return 0
  else:
    matrix[x][y] = -1
    
    for i in range(4):
      if 0 <= x + dx[i] < len(matrix) and 0 <= y + dy[i] < len(matrix[0]):
        DFS((x+dx[i], y+dy[i]), matrix)

    return 1
  
if __name__ == '__main__':
  T = int(input())
  
  for i in range(T):
    row, col, count = map(int, input().split())
    cabbage = [list(map(int, input().split())) for _ in range(count)]
    matrix = [[0] * col for _ in range(row)]
    ans = 0

    for node in cabbage:
      x, y = node
      matrix[x][y] = 1

    for node in cabbage:
      ans += DFS(node, matrix)

    print(ans)

 

로직은 반복문으로 배추가 있는 위치를 넣어서 DFS로 전부 방문하고

방문하지 않은 배추일 때만 ans에 1씩 더해주도록 만들었다.

첫 번째 풀이와 다른 점은 재귀 한계를 풀어주었다는 점이다.

 

---

 

시간 복잡도

 

-

 

알게 된 점

 

RecursionError는 Python이 정한 최대 재귀 깊이보다 더 깊어질 때 발생한다.

이를 해결하는 방법은 2가지가 있는데

 

1. 파이썬의 최대 재귀 깊이를 늘려주는 방법

2. 반복문으로 대체하여 구현하는 방법

 

이 있다.

 

1. 파이썬의 최대 재귀 깊이를 늘려주는 방법

 

import sys
sys.setrecursionlimit(10**6)

# sys.getrecursionlimit() 최대 재귀 깊이 확인

 

sys 라이브러리의 sys.setrecursionlimit 함수를 통해 파이썬의 최대 재귀 깊이를 늘려줄 수 있다.

 

2. 반복문으로 대체하여 구현하는 방법

 

모든 재귀함수는 반복문으로 구현할 수 있고, 모든 반복문은 재귀함수로 구현할 수 있다.

 

if __name__ == '__main__':
  T = int(input())
  
  for i in range(T):
    row, col, count = map(int, input().split())
    cabbage = [list(map(int, input().split())) for _ in range(count)]
    matrix = [[0] * col for _ in range(row)]
    ans = 0

    for node in cabbage:
      x, y = node
      matrix[x][y] = 1

    for node in cabbage:
      dx = [1, -1, 0, 0]
      dy = [0, 0, 1, -1]
      x, y = node
      stack = []

      if matrix[x][y] <= 0:
        continue

      stack.append((x, y))

      ans += 1
      
      while len(stack):
        x, y = stack.pop()
        matrix[x][y] = -1
        
        for i in range(4):
          x2 = x + dx[i]
          y2 = y + dy[i]
          
          if 0 <= x2 < len(matrix) and 0 <= y2 < len(matrix[0]):
            if matrix[x2][y2] > 0:
              stack.append((x2, y2))

    print(ans)

 

1. 현재 위치에 대해서 방문체크를 한다.

2. 이후 이 위치에서 사방을 살펴보고, 방문하지 않은 위치가 있다면 stack에 넣는다.

3. 모든 stack의 길이가 0보다 크다면 stack에서 노드를 빼서 반복한다.

 

queue를 이용하면 BFS로도 구현할 수 있다.

 

 

고찰

 

-