[백준] 1520 내리막길 / DP / Python / 골3

부제: 무한 런타임 에러 해결하기

 

처음에 접근하려고 했던건 

 

<틀린풀이>

 

일단 현재 위치가 0이 아니어야 어딘가로부터 이동경로를 받을 수 있다는 뜻

그래서 0이 아닌 경우에만 탐색함

 

상하좌우에서 현재 위치로 이동하는 경우에

상하좌우에서 받을 수 있는 max값을 현재 위치의 이동 가능 경로로 세팅해둠

 

그리고 현재 위치에서 상,하,좌,우로 이동할 때 현재 수보다 이동한 위치의 수가 작으면 내리막길이니까

이동 가능 경로 개수를 업데이트 해주고 싶음

각 상하좌우로 이동했을 때 위치에다가

현재 위치의 이동 경로 개수를 그대로 받는 경우 또는... 이동한 위치의 이동 경로 개수+1 값을 비교해서

max값으로 업데이트를 해줬음

 

<틀린풀이>

 

m,n = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(m)]

dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0]=1

for i in range(m):
    for j in range(n):
        left=0
        right=0
        down=0
        print(f'현재는 {i} {j} 원소값은 {dp[i][j]}')
        if dp[i][j]!=0:
            if j+1<n and arr[i][j+1]-arr[i][j]>0:
                dp[i][j]=max(dp[i][j], dp[i][j+1])
                print(f'우측 탐색 {i},{j+1} 원소값 {dp[i][j+1]}')
            if i+1<m and arr[i+1][j]-arr[i][j]>0:
                dp[i][j]=max(dp[i][j],dp[i+1][j])
                print(f'하단 탐색 {i+1},{j} 원소값 {dp[i+1][j]}')
            if j-1>0 and arr[i][j-1]-arr[i][j]>0:
                dp[i][j]=max(dp[i][j],dp[i][j-1])
                print(f'좌측 탐색 {i},{j-1} 원소값 {dp[i][j-1]}')
            if i-1>0 and arr[i-1][j]-arr[i][j]>0:
                dp[i][j]=max(dp[i][j],dp[i-1][j])
                print(f'상단탐색 {i-1},{j} 원소값 {dp[i-1][j]}')
            if j+1<n and arr[i][j]-arr[i][j+1]>0:
                dp[i][j+1]=max(dp[i][j], dp[i][j+1]+1)
                print(f'우측 탐색 {i},{j+1} 원소값 {dp[i][j+1]}')
            if i+1<m and arr[i][j]-arr[i+1][j]>0:
                dp[i+1][j]=max(dp[i][j],dp[i+1][j]+1)
                print(f'하단 탐색 {i+1},{j} 원소값 {dp[i+1][j]}')
            if j-1>0 and arr[i][j]-arr[i][j-1]>0:
                dp[i][j-1]=max(dp[i][j],dp[i][j-1]+1)
                print(f'좌측 탐색 {i},{j-1} 원소값 {dp[i][j-1]}')
            if i-1>0 and arr[i][j]-arr[i-1][j]>0:
                dp[i-1][j]=max(dp[i][j],dp[i-1][j]+1)
                print(f'상단탐색 {i-1},{j} 원소값 {dp[i-1][j]}')

print(dp)
print(dp[m-1][n-1])

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

현재는 0 0 원소값은 1
우측 탐색 0,1 원소값 1
하단 탐색 1,0 원소값 1
현재는 0 1 원소값은 1
하단 탐색 1,1 원소값 0
우측 탐색 0,2 원소값 1
현재는 0 2 원소값은 1
하단 탐색 1,2 원소값 0
좌측 탐색 0,1 원소값 1
우측 탐색 0,3 원소값 1
현재는 0 3 원소값은 1
좌측 탐색 0,2 원소값 1
우측 탐색 0,4 원소값 1
하단 탐색 1,3 원소값 1
현재는 0 4 원소값은 1
좌측 탐색 0,3 원소값 1
하단 탐색 1,4 원소값 1
현재는 1 0 원소값은 1
우측 탐색 1,1 원소값 0
하단 탐색 2,0 원소값 1
현재는 1 1 원소값은 0
현재는 1 2 원소값은 0
현재는 1 3 원소값은 1
우측 탐색 1,4 원소값 1
좌측 탐색 1,2 원소값 0
하단 탐색 2,3 원소값 1
현재는 1 4 원소값은 1
하단 탐색 2,4 원소값 0
좌측 탐색 1,3 원소값 2
현재는 2 0 원소값은 1
상단탐색 1,0 원소값 1
하단 탐색 3,0 원소값 1
현재는 2 1 원소값은 0
현재는 2 2 원소값은 0
현재는 2 3 원소값은 1
우측 탐색 2,4 원소값 0
좌측 탐색 2,2 원소값 0
상단탐색 1,3 원소값 2
하단 탐색 3,3 원소값 2
현재는 2 4 원소값은 0
현재는 3 0 원소값은 1
상단탐색 2,0 원소값 1
우측 탐색 3,1 원소값 1
현재는 3 1 원소값은 1
상단탐색 2,1 원소값 0
우측 탐색 3,2 원소값 1
현재는 3 2 원소값은 1
좌측 탐색 3,1 원소값 1
상단탐색 2,2 원소값 0
우측 탐색 3,3 원소값 3
현재는 3 3 원소값은 3
좌측 탐색 3,2 원소값 1
상단탐색 2,3 원소값 2
우측 탐색 3,4 원소값 3
현재는 3 4 원소값은 3
좌측 탐색 3,3 원소값 3
상단탐색 2,4 원소값 0

[[1, 1, 1, 1, 1], [1, 0, 0, 2, 1], [1, 0, 0, 2, 0], [1, 1, 1, 3, 3]]  
3

 

예제 케이스에서는 맞았지만

채점 9%에서 틀렸다고 뜸

 

일단 dp를 스스로도 엉성하게 구현했다고 생각했기 때문에...

 

무슨 방법이 좋을지 고민했음

 

근데 알고보니 이거...

DP로만 못풂... DFS 결합해야됨

 

처음에 문제 자체가 너무 그래프같이 생겼지만 DP 분류라 DP로 풀려고 했는데

뒤통수 맞은 기분이었음...

 

dfs에 y,x 좌표를 넣고

만약 dp[y][x] 값이 존재하면 바로 return하고

 

만약 dp[y][x]값이 아직 세팅되지 않은 상태면

해당 위치의 상하좌우를 탐색해서, 내리막길일 경우에

dp[y][x]에 그 내리막길인 원소의 좌표를 dfs로 구한 값을 더해준다

 

그 작업이 끝나면 dp[y][x]를 return한다

 

이런식으로 dp각 원소에 대해 dfs를 수행하는 방식으로 풀어야한다

(배신감....느껴져)

 

중요!!! 런타임에러 없애려면

sys.setrecursionlimit(10 ** 9)

 

이걸 추가해서 재귀리밋을 걸어야함!!!!!!

저거 안걸면 아무리 맞게 풀어도 런타임 에러 뜸....

 

파이썬의 기본 재귀 제한은 1000으로 매우 얕은 편이라고 한다

그래서 그 제한을 늘려줘야 원하는대로 dfs 탐색을 온전히 할 수 있는 것이다...

 

이것 때문에 거의 1시간 날린 듯

 

import sys
sys.setrecursionlimit(10 ** 9)
m,n = map(int,sys.stdin.readline().split())
arr = [list(map(int,sys.stdin.readline().split())) for _ in range(m)]

dp = [[-1]*n for _ in range(m)]
dp[-1][-1]=1

dx=[0,0,1,-1]
dy=[1,-1,0,0]
def dfs(y,x):
    if y==m-1 and x==n-1:
        return 1

    if dp[y][x]==-1:
        dp[y][x]=0
        for i in range(4):
            ay,ax = y+dy[i], x+dx[i]
            if -1<ax<n and -1<ay<m and arr[y][x]>arr[ay][ax]:
                dp[y][x]+=dfs(ay,ax)
    return dp[y][x]

print(dfs(0,0))