[1520] 내리막 길 in python

ㅎr....

dp는 왤케 어려운걸까..

머리가 돌아가지 않는다아...

 

이 문제 딱 보는 순간

dfs 문제라는 걸 직감하였디!

 

그래도 문제 풀면 풀수록 

나아지는 게 느껴져서 행복하다..

(물론 아직 갈길이 멀긴 하지만!)

 

 

이 문제는

처음부터 이해를 잘못했었다..

역시 나답다 ^_^

 

 

현재 높이보다 작은 곳으로 이동하는건데

가장 작은 높이들만 찾아서 이동하는 건줄 알았다 ^0^..

 

---

예시를 가지고 풀이 시작!

 

총 3가지의 경우의 수가 있다!

 

 

1번째 경로

50 -> 45 -> 37 -> 20 -> 17 -> 15 -> 10

0	0	0	1	1
-1	-1	-1	1	1
-1	-1	-1	1	-1
-1	-1	-1	1	-1

 

2번째 경로

50 -> 45 -> 37 -> 32 -> 20 -> 17 -> 15 -> 10

2	2	2	2	1
-1	-1	-1	1	1
-1	-1	-1	1	-1
-1	-1	-1	1	-1

 

3번째 경로

50 -> 35 -> 30 -> 27 -> 24 -> 22 -> 15 -> 10

3	2	2	2	1
1	-1	-1	1	1
1	-1	-1	1	-1
1	1	1	1	-1

n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]
visited = [[-1 for _ in range(m)] for _ in range(n)]
# 상,우,하,좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 항상 지금의 높이보다 높이가 더 낮은 지점으로만 이동한다.
# 항상 내리막길로만 이동하는 경로의 수를 구하라
answer = 0

# 맨 오른쪽 좌표 : n-1, m-1
def dfs(x, y):
    global answer
    if x == n - 1 and y == m - 1:
        return 1
    if visited[x][y] != -1:
        return visited[x][y]
    visited[x][y] = 0 # 현재 위치 방문처리 과정    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            # 맵 안에 있는 경우
            if array[nx][ny] < array[x][y]:
                visited[x][y] += dfs(nx, ny)
    print(visited)
    return visited[x][y]


print(dfs(0, 0))