글 읽기 - recursion error 가 뜨는 이유가 뭘까요..ㅠ

cipher8 3년 전 0

문제의 케이스나

1 1 1

이런케이스들 다 답이 잘 나옵니다.

그런데 제출하면 5퍼센트 근처에서 RecursionError 내고 뻗네요..

어디를 놓친걸까요?

n= int(input())
graph =[] 

for _ in range(n):
  graph.append(list(map(int, input().split())))

# print(visit)
# print(graph)

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

def dfs(x,y, rain, visit):
  for c in range(4):
    nx= x+dx[c]
    ny= y+dy[c]
    if (0<=nx<n) and (0<=ny<n) and visit[nx][ny]==0 and graph[nx][ny]>rain:
      visit[nx][ny]=1
      # print(visit)
      dfs(nx, ny, rain, visit)
  return visit

def findSafePlace(rain):
  res =0
  visit = [[0]*n for _ in range(n)] 
  for i in range(n):
    for j in range(n):
      if visit[i][j]!=1 and graph[i][j]>rain:
        visit[i][j]=1
        dfs(i,j,rain, visit)
        res+=1
  return res

solution=[]
for c in range(max(map(max,graph))):
  # print(c)
  solution.append(findSafePlace(c))
  

print(max(solution))

cipher8 3년 전 1

자문자답입니다. 이게 시간복잡도가 O(n^3) 이다보니 케이스 수가 커지면 파이썬의 기본 recursion limit에 걸립니다.

import sys

sys.setrecursionlimit(100000)

이런식으로 recursion limit을 늘려주면 잘 돌아갑니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

recursion error 가 뜨는 이유가 뭘까요..ㅠ

cipher8 3년 전 0

cipher8 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말