[백준] 1520 내리막길

📖 문제

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

💻 내 코드

import sys
sys.setrecursionlimit(10 ** 8)

n, m = map(int, sys.stdin.readline().split())

mlist = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
route = [[-1]*m for _ in range(n)]
dx = [-1,0,1,0]
dy = [0,-1,0,1]
visited = [[False]*m for _ in range(n)]
def find(x, y):

    if x==n-1 and y==m-1:
        return 1
    if route[x][y]!=-1:
        return route[x][y]
    res=0
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]

        if 0<=nx<n and 0<=ny<m and mlist[nx][ny]<mlist[x][y]:
            res+=find(nx, ny)
    route[x][y]=res
    return route[x][y]



print(find(0,0))

💡 풀이

• 모르겠어서 다른 사람들 풀이 참고함

• dfs를 돌면서 좌표가 x=n-1, y=m-1일때만 cnt를 더해주는 식을로 먼저 풀었었는데 그렇게 하면 시간초과가 난다

• 찾아보니깐 끝까지 갈 수 없는 경로도 계속해서 탐색하기 때문이라고 했다

• 그렇다고 이 탐색을 없애기 위해 visited 배열로 방문한 곳을 True로 표시해주면 안됨

  • 다시 방문할 수 있기 때문
  • dp가 필요

• dp 배열을 모두 -1로 초기화

• 만약 현재 좌표의 dp좌표가 -1이라면 아직 탐색을 하지 않았으므로 탐색을 진행

• 사방에서 자신보다 더 작은 좌표를 발견하면 그 곳에서 다시 dfs 탐색 진행

• 계속 진행하다 도착지점으로 가면 1을 반환한다

• 재귀함수를 통해 호출한 것이기 때문에 현재 지나온 곳의 모든 경로에 경로의 수로 업데이트 된다

• 탐색을 진행하며 만약 -1이 아닌 곳을 만나게 되면 이미 지나간 경로이기 때문에 그 곳은 탐색할 필요 없이 경로의 수만 반환해주면 된다