[BOJ 1520] 내리막 길

문제는 여기

 

1520 내리막길 문제는, 제가 무려 2년 전에 틀려놓고 그뒤로 방치했던 문제입니다.

 

무시무시한 런타임에러...

 

그래서 이제와서 다시 재도전해보려고 켜봤습니다.

 

문제 자체는 말이 쉽습니다. 숫자들이 주어지고, 대충 그걸 높이라고 치면 쭉 내리막길이 되도록 잘 내려가는 루트가 몇개나 있는지, 찾으면 되는 문제입니다. 너무 대놓고 '나 DP예요 DP!'라고 광고하는 거 아닌가 싶을 정도의 문제입니다.

 

대충 첫칸부터 시작해서 DPS로 탐색을 하는데, 이미 방문한 적 있는 곳이면 기록을 미리 해두고 그곳으로 가는 내리막길이 있음+그길로 가면 끝까지 갈 수 있음이면 그 경우의 수만큼 더해주면 되는 간단한 코드를 생각할 수 있습니다.

 

구현 자체는 크게 어렵지 않았습니다.

 

m,n=map(int,input().split())
L=[]
for i in ' '*m:L.append(list(map(int,input().split())))
dp=[[-1]*n for i in range(m)] #방문 여부 표시를 위해서 -1로 초기화
x,y=0,0
def solve(y,x):
    global L
    global dp
    if not(0<=x<n) or not(0<=y<m):
        return 0 #칸 벗어나면 0으로
    if x==y==0:return 1 #마지막칸은 1로
    if dp[y][x]!=-1:return dp[y][x] #이미 방문했으면 그냥 그걸로
    else:
        dp[y][x]=0
        for i in range(4):
            dirx,diry=[[0,1],[1,0],[0,-1],[-1,0]][i]
            newx=dirx+x
            newy=diry+y
            if 0<=newx<n and 0<=newy<m:
                if L[y][x]<L[newy][newx]: #새로 간 곳이 내리막길이면
                    dp[y][x]+=solve(newy,newx) #더해준다
    return dp[y][x]
print(solve(m-1,n-1))

하지만 어림도 없지! 또 또 런타임에러가 떴습니다.

문제가 무엇인고 생각해봤더니, 제가 너무 생각없이 재귀함수를 썼습니다.

 

파이썬에서는 대충 재귀를 1000번 정도까지만 할 수 있는데, 최대 500*500짜리가 나올 수 있으니까 당연히 넘어버릴 수도 있습니다. 그걸 감안하지 않고 무작정 재귀로 짜버린 탓이 되었네요.

 

물론 이 문제는 해결할 수 있는 방법이 있습니다. 그냥 recursion depth 상한을 건드려주면 됩니다.

 

import sys
sys.setrecursionlimit(10000)

대충 이걸 코드 아무데나 집어넣으면 재귀 상한을 건드릴 수 있습니다. 사실 10000도 살짝 위험한데(25000칸까지 가능하니까)그래도 이걸로 통과가 되더라고요. 더 큰 숫자 넣어도 당연히 괜찮습니다.

 

그래서 드디어 정답을 얻어낼 수 있었습니다.

 

C++로는...그냥 나중에 해봐야 할 것 같습니다. 사실 저렇게 recursion depth 설정할 필요도 없을테니까 오히려 더 간편할 수도 있을 것 같습니다.