백준 1520 내리막길 파이썬 문제풀이 (python 2차원 DP)

문제 보러가기

 

백준 내리막길 파이썬 문제풀이

0,0에서 시작해서 최우측 최하단으로 이동하는 방법 중에 숫자가 더 작은 칸으로만 이동하는 방법으로 

몇 가지가 있는지 구하는 문제이다.

 

위 경우는 이렇게 3가지 뿐이다.

 

탐색의 방법처럼 4방향으로 하나씩 이동해서 재귀적으로 탐색하는데,

경로를 어떻게 dp에 담는지가 관건이다.

 

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

def recur(y,x):

    if y == m-1 and x == n-1:
        return 1

    route = 0
    for dy, dx in [[0,1], [0,-1],[1,0], [-1,0]]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < m : # 범위 내 존재
            if map[ny][nx] < map[y][x]: # 높이가 지금보다 더 높은 곳으로(반대로 이동)
                # route += recur(ny,nx)
                dp[y][x] += recur(ny,nx)
    #dp[y][x] = route
    
    return dp[y][x]

recur(0,0)

#for d in dp:
    #print(d)

print(dp[0][0])

주석처리한 코드가 맞는 방법이고 위 코드는 잘못된 방법이다.

처음에는 이 코드가 왜 안되는지 고민했다.

 

 

결과는 이렇게 나오는데,

각 칸에서 최우측하단으로 이동할 수 있는 방법들이

갈림길마다 누적되고 중복되어서 숫자가 겹치는 현상 때문에

이렇게 된다.

 

15번에서 갈 수 있는 방법은 총 3개이고, 여기서 갈라지는 양쪽 방향 모두 3이 값으로 전달되었다.

이게 길이 갈라지면 또 개수가 더해지고 해서 첫 칸에 8로 커져버린다.

코드

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

def recur(y,x):

    if y == m-1 and x == n-1:
        return 1

    route = 0
    for dy, dx in [[0,1], [0,-1],[1,0], [-1,0]]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < m : # 범위 내 존재
            if map[ny][nx] < map[y][x]: # 높이가 지금보다 더 높은 곳으로(반대로 이동)
                route += recur(ny,nx)
                #dp[y][x] += recur(ny,nx)
    dp[y][x] = route
    return dp[y][x]

recur(0,0)

#for d in dp:
    #print(d)

print(dp[0][0])

올바른 방법은 route로 4방향 중 몇 개가 끝까지 갔는지를 

체크하는 것이다.

 

각 dp 칸에는 현재 칸에서 끝까지 도착하는 루트가 몇 개인지만 세어야한다.

해당 칸부터 끝까지 도착하는 루트가 하나라면 1이고, 

서로 다르게 갈라지면 1 이상으로 올라간다.

 

하지만 재귀에서 recursion error가 떴다.

 

재귀의 수를 줄여야한다. 

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

def recur(y,x):

    if y == m-1 and x == n-1:
        return 1

    if dp[y][x] != 0:
        return dp[y][x]

    route = 0
    for dy, dx in [[0,1], [0,-1],[1,0], [-1,0]]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < m : # 범위 내 존재
            if map[ny][nx] < map[y][x]: # 높이가 지금보다 더 높은 곳으로(반대로 이동)
                route += recur(ny,nx)
                #dp[y][x] += recur(ny,nx)
    dp[y][x] = route
    return dp[y][x]

recur(0,0)

# for d in dp:
#     print(d)

print(dp[0][0])

0이 아니라 dp값이 이미 있으면 return하도록 했지만,

여전히 오류가 생긴다.

아무래도 재귀 제한에 걸린 것 같다. 

정답코드 

import sys
sys.setrecursionlimit(100000)

m,n = map(int,input().split())
map = [list(map(int,input().split())) for _ in range(m)]
dp = [[-1] * n for _ in range(m)]

def recur(y,x):

    if y == m-1 and x == n-1:
        return 1

    if dp[y][x] != -1:
        return dp[y][x]

    route = 0
    for dy, dx in [[0,1], [0,-1],[1,0], [-1,0]]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < m : # 범위 내 존재
            if map[ny][nx] < map[y][x]: # 높이가 지금보다 더 높은 곳으로(반대로 이동)
                route += recur(ny,nx)
                #dp[y][x] += recur(ny,nx)
    dp[y][x] = route
    return dp[y][x]

recur(0,0)

# for d in dp:
#     print(d)

print(dp[0][0])

정답 코드에서는 두 가지가 바뀌었다.

우선 dp의 초기값이 0인 경우, 마찬가지로 갈 수 있는 방향이 없어서 값이 0이 되는 칸들 때문에 반복하는 경우가 생긴다.

때문에 -1을 초기값으로 하여 이러한 상황을 없앤다.

 

또, recursion limit를 높여서 재귀 스택이 오버되지 않도록 한다.

이제서야 맞았다~