백준 1520 내리막 길 파이썬 풀이

난이도 : 골드3

풀이일 : 2403133

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

1520번: 내리막 길

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys
sys.setrecursionlimit(10**9)


def sol(i, j):
    # 목적지 도착 시 1 반환
    if i == N - 1 and j == M - 1:
        return 1

    # 방문한 적이 있다면 dp[i][j] 반환
    if dp[i][j] != -1:
        return dp[i][j]

    # 방문여부 표시
    dp[i][j] = 0
    # 상하좌우 탐색
    for k in range(4):
        ni, nj = i + di[k], j + dj[k]
        # world 배열안에 있고, 현재값보다 작은 값에 대해 재귀 탐색
        if 0 <= ni < N and 0 <= nj < M:
            if world[i][j] > world[ni][nj]:
                # 목적지에 가는 모든 경로의 수 더하기
                dp[i][j] += sol(ni, nj)
    # 현재 위치에서 목적지에 가는 경로의 수 반환
    return dp[i][j]


N, M = list(map(int, sys.stdin.readline().split()))
world = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [[-1] * M for _ in range(N)]
di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]

print(sol(0, 0))

• dp : 현재 위치에서 도착지까지 갈 수 있는 경로의 수를 저장하는 2차원 배열
  • 방문 여부 확인을 위한 초기 값은 경로가 0개인 경우를 고려해 -1로 설정
• di, dj : 상하좌우 탐색을 위한 방향좌표
• sol : DFS 재귀 호출로 목적지부터 현재 위치까지 이어지는 경로를 반환

---

느낀점

• BFS로 deque를 사용해서 빠르게 풀었다가, 예전에 틀린 적이 있길래 BFS는 아니구나 싶어서 다른 방법을 고민해 dp로 풀었다. 배낭 문제 이후로 오랜만에 dp를 보는 것 같은데 재밌어서 dp 문제들을 좀 찾아서 풀어봐야지 싶다.