[Python] 1520 - 내리막 길 (골드4)

1. 문제 설명

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

---

2. 아이디어

이게 왜 골드4..? 라는 생각이 들 정도로 아이디어나 알고리즘이나 딱히 특출날 게 없는 문제.

source와 sink가 고정정으로 좌상단, 우하단으로 정해져 있기 때문에

dfs를 사용하여 각 지점에서 종점으로 갈 수 있는 경우를 dp로 저장해가면서

마지막에 (0,0)에 할당되는 결과값을 출력하면 끝난다.

 

다만, 내가 여기서 처음 틀렸던 이유는 cache를 0으로 초기화 했었는데

돌다보면 0이라는 정보가 "경우의 수가 없음"을 의미하는 건지, 아직 "경우의 수를 구하지 않음"을 의미하는지

구분이 안 가다보니 엉뚱한 결과가 출력되거나 불필요한 연산을 지속하게 되었던 것으로 기억한다.

 

물론 다른 코드를 짰다면 나와 같은 이슈로 틀리지 않을 수 있긴 하지만 dp를 초기화하는 값 또한

중요하다는 것을 알 수 있게된 문제였다.

 

---

3. 코드

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

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

def dfs(row, col):
    if row == n - 1 and col == m - 1:
        return 1
    if cache[row][col] == -1:
        cache[row][col] = 0
        for q, p in vector:
            m_y = row + q
            m_x = col + p
            if 0 <= m_y < n and 0 <= m_x < m:
                if paper[row][col] > paper[m_y][m_x]:
                    cache[row][col] += dfs(m_y, m_x)
    else:
        return cache[row][col]
    return cache[row][col]    

def solution():
    print(dfs(0, 0))

solution()