글 읽기 - [python] recursion error가 계속 되네요 ㅠ

kan5995 1년 전 0

질문 게시판에 올라와 있는 반례들 한 번씩은 다 해본 것 같은데,

자꾸만 recursion error로 뜨니깐 속상하네요 ㅠㅠ

혹시 어떤게 문제일까요??

알고리즘은 이렇습니다.

1) Row나 Column 중에 홀수가 있다면 : 그렇지 않은 쪽부터 우선적으로 돈다. (RRRDLLLD.. 등)

2) 만약 둘다 짝수라면,

3) minVal 을 행과 열의 index합이 홀수인 위치 중에서 가장 작은 값으로 정의하고, 그 때의 좌표를 x,y에 넣어둔다.

4) dfs를 이용해서 (x,y)가 아니고, 전체 r*c-2 개를 모두 통과하여 도착점에 도달한 경우에, 해당 경로를 담고 있는 answer를 리턴하도록 지시한다.

고수님들 도와주세요 ㅠㅠ

r,c = map(int, input().split())
if r % 2:
	answer = "R"*(c-1)
	for i in range(r-1):
		tmp = "R"
		if i % 2 == 0:
			tmp = "L"
		answer += "D"+tmp*(c-1)
	print(answer)
	exit(0)
if c % 2:
	answer = "D"*(r-1)
	for i in range(c-1):
		tmp = "D"
		if i % 2 == 0:
			tmp = "U"
		answer += "R"+tmp*(r-1)
	print(answer)
	exit(0)
MAP = []
for _ in range(r):
	MAP.append(list(map(int, input().split())))

minval = float('inf')
x,y = 0,0
for i in range(r):
	for j in range(c):
		if (i+j)%2==1 and minval > MAP[i][j]:
			minval = MAP[i][j]
			x,y=i,j

visited = [[False for _ in range(c)] for _ in range(r)]
dic = {(-1,0):"U", (0,1):"R", (0,-1):"L", (1,0):"D"}
def dfs(i,j,visited, answer):
	if i == x and j == y:
		return None
	if i == r-1 and j == c-1:
		if len(answer) == r*c-2:
			return answer
		return None
	visited[i][j] = True
	for dx, dy in [(-1,0),(0,-1),(0,1),(1,0)]:
		nx, ny = i+dx, j+dy
		if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
			visited[nx][ny] = True
			value = dfs(nx,ny,visited,answer+dic[(dx,dy)])
			if value:
				return value
			visited[nx][ny] = False
visited[0][0] = True
print(dfs(0,0,visited,""))

dhyang24 1년 전 0

import sys
sys.setrecursionlimit(10**6)

recursionerror는 보통 할당된 recursion 메모리보다 많은 횟수만큼 함수가 재귀호출되었을때 일어납니다

위 코드를 코드 맨 처음에 추가해 보세요

dhyang24 1년 전 0

그래도 해결되지 않는다면 sys.setrecursionlimit() 안의 숫자를 좀 더 늘려서 시도해 보시거나,
아니면 함수가 모종의 이유로 루프하고 있을 수 있습니다.

kan5995 1년 전 0

말씀 감사합니다

조언해주신대로 setrecursionlimit을 바꿔가며 대입했더니, 이젠 메모리 초과가 뜨네요.

아무래도 dfs로 1000 * 1000짜리 graph를 도는게 무리인가보네요 ㅎㅎ

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

문제

문제

출처

ICPC

[python] recursion error가 계속 되네요 ㅠ

kan5995 1년 전 0

dhyang24 1년 전 0

dhyang24 1년 전 0

kan5995 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말