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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

m, n = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(m)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


# dp[r][c] = (r, c)에서 (m-1, n-1)까지 갈 수 있는 경로의 수
# 방문하지 않았을 때는 -1로 초기화
# 시간초과를 피하기 위해 DP + DFS 전략
dp = [[-1] * n for _ in range(m)]


def dfs(r, c):
    # 도착점에서 도착점으로 갈 수 있는 경로의 수는 1
    if r == m-1 and c == n-1:
        dp[r][c] = 1

    # 방문 기록이 있으면 return
    if dp[r][c] != -1:
        return dp[r][c]

    # 아직 방문하지 않음 -> 0으로 업데이트
    if dp[r][c] == -1:
        dp[r][c] = 0

    for i in range(4):
        new_r = r + dx[i]
        new_c = c + dy[i]
        if 0 <= new_r < m and 0 <= new_c < n:
            if board[new_r][new_c] < board[r][c]:
                dp[r][c] += dfs(new_r, new_c)

    return dp[r][c]


print(dfs(0, 0))
# print(dp)

---

🧂아이디어

탐색, DP

• 딱 보고 DFS로 풀이하면 된다는 생각을 떠올리기는 쉽지만, 그냥 DFS로만 풀면 시간초과 혹은 recursion error가 뜬다
  • 왜?
  • 재귀가 이루어질 때마다 4번의 탐색이 발생한다. 최악의 경우 4^(500*500)번의 탐색이 일어난다.

• 위와 같은 엄청난 횟수의 탐색을 피하기 위해 DFS + DP 전략을 쓴다
  • dp[r][c] = (r, c) 지점에서 도착점인 (m-1, n-1)까지 갈 수 있는 경로의 수
  • 아직 방문하지 않았을 때는 dp[r][c] = -1로 초기화
  • dfs를 다 해 볼 필요 없이, dp[r][c]의 값이 있다면 바로 리턴한다
  • dp[r][c] += dfs(new_r, new_c)

• 혹시 설명이 부족하다면 아래 링크 참고! 애니메이션도 있는데 매우 이해하기 좋다 최고최고

  매우참고❤: https://wootool.tistory.com/83

🧐

• 4차시도까지는 dfs로 계속 시도했지만 실패😋
• 5차 시도는 dp+dfs 알고리즘을 적용했으나 recursion limit을 늘려주지 않았음
• 6차 시도(맞았습니다!!) 는 dp + dfs 알고리즘도 적용하고, recursion limit도 잊지 않고 늘려줌