❌ 나의 코드 (DFS)

# 나의 풀이 Only DFS

import sys
input = sys.stdin.readline

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

dx = [0, 0, 1]
dy = [1, -1, 0]


def dfs(x, y):
    global ans
    if x == m-1 and y == n-1:
        ans += 1
        return
    
    for i in range(3):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0<= ny < n and map[x][y] > map[nx][ny]:
            dfs(nx, ny)

dfs(0, 0)
print(ans)

✅ 정답 코드 (DFS x DP)

# 정답 DFS X DP
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def dfs(sx, sy):
    # 도착 지점에 도달하면 1(한 가지 경우의 수)를 리턴
    if sx == m-1 and sy == n-1:
        return 1

    # 이미 방문한 적이 있다면 그 위치에서 출발하는 경우의 수를 리턴
    if dp[sx][sy] != -1:
        return dp[sx][sy]
    
    ways = 0
    for i in range(4):
        nx, ny = sx + dx[i], sy + dy[i]
        if 0 <= nx < m and 0 <= ny < n and graph[sx][sy] > graph[nx][ny]:
            ways += dfs(nx, ny)
    
    dp[sx][sy] = ways
    return dp[sx][sy]


m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]
dp = [[-1] * n for _ in range(m)]
dx, dy = [1,-1,0,0], [0,0,1,-1]
print(dfs(0,0))
print(dp)

🤔 틀린 이유

• 틀린 이유

1. DFS로 테케는 맞췄으나, 시간복잡도 측면에서 시간초과가 남
   why? 500 * 500 에서 상하좌우 4가지 방향을 한 블럭마다 다 해주면 시간초과가 2초인 문제에서
   당연히 에러가 발생함 ,, 이 부분을 깊게 생각하지 않음 (문제를 오랜만에 풀어서 그런듯)

2. 시간 복잡도를 낮추려면 ? 불필요한 연산 수를 줄여야 함 ,,
   How? 전체 문제의 최적해가 부분 문제의 최적해로 쪼개질 수 있도록 해야 함 (블럭으로 생각하면 이해 OK)

🎈 그림을 그려보며 알고리즘 이해해보기

• 잘 안보여서 아래에 다시 기술함

1. 첫 번째 경로(빨간색 선)에 의해서 M = -1 에서 M = 1로 변경 (M이란 빨갛게 동그라미 친 부분)
2. 두 번째 경로 역시 M을 거치게 되는데, M = 1로 -1이 아니기 때문에 4가지 방향 탐색을 진행하지 않음
   즉, 뭐다? 불필요한 연산을 진행하지 않는다 !
3. 세 번째 경로 역시 M을 거치지만, M이 채워져 있어서 연산을 하지 않음

• 테스트 케이스만 보면 이게 무슨 큰 영향을 줄 수 있나? 라는 생각을 들 수 있지만, 저 (0,0)지점이 M이 된다면 얼마나 시간복잡도를 줄일까?
• 맵의 크기가 크면 클수록 엄청 큰 효과있을 것이다! 따라서, 테케 하나만 준 백준이 잘못한거다 ~

🌟 느낀 점

1. 불필요한 연산을 어떻게 줄일지를 생각해보기 (이 부분은 .. 음 문제를 더풀면서 길러질듯)
2. 답을 보면서도 이해하는데 시간이 좀 걸린 것 같은데, 그림 그리면 바로 이해됌 - 이해안되면 위와 같이 그림그리며 이해해보기