BOJ 1012 유기농 배추 Python

일반적인 DFS 문제이며, 재귀를 이용한 DFS 구현으로 풀었다.

맨 처음에 Recursion error가 발생했는데, 백준에서 재귀를 1000 이하로만 설정하지만, 2500번의 재귀가 발생할 수 있으므로 설정 값을 바꿔줌으로서 해결했다.

 

아래는 코드이다.

import sys
sys.setrecursionlimit(10**6)

def dfs(x, y, graph):
  if x <= -1 or y <= -1 or x >= len(graph) or y >= len(graph[0]):
    return 0

  if graph[x][y] == 1:
    graph[x][y] = 0
    dfs(x + 1, y, graph)
    dfs(x, y + 1, graph)
    dfs(x - 1, y, graph)
    dfs(x, y - 1, graph)
    return 1
    
  return 0
  
def solve():
  vert, horz, plant = map(int, input().split())
  graph = [[0 for i in range(horz + 1)] for j in range(vert + 1)]
  worm = 0

  for i in range(plant):
    x, y = map(int, input().split())
    graph[x][y] = 1

  for n, i in enumerate(graph):
    for m, j in enumerate(i):
      if j == 1:
        worm += dfs(n, m, graph)
  print(worm)
for i in range(int(input())):
  solve()