[백준] 1520번 내리막길 - 파이썬(Python)

문제 (링크)

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

1520번: 내리막 길

 

나의 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
graph = []

moves = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1]
]

visited = [[-1] * m for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int, input().split())))

def dfs(x, y):
    # Base Case
    if x == n - 1 and y == m - 1:
        return 1
    
    # 이미 방문한 곳일 때
    if visited[x][y] != -1:
        return visited[x][y]

    visited[x][y] = 0

    for move in moves:
        nx, ny = x + move[0], y + move[1]

        if 0 <= nx < n and 0 <= ny < m:
            if graph[x][y] > graph[nx][ny]:
                visited[x][y] += dfs(nx, ny)

    return visited[x][y]

print(dfs(0, 0))

코드설명 및 풀이법

처음엔 (0, 0)에서 시작해 DFS로 가능한 곳을 모두 탐색하였지만 그렇게 하면 시간초과가 났다.

 

시간초과를 줄이기 위한 핵심은 DFS에 DP 방식을 결합하는 것인데, 피보나치 수열을 DP방식으로 해결하는 것과 비슷한 아이디어이다.

 

visited 배열에 -1, 0, n을 이용해서 각각 방문하지 않은 경우, 방문한 경우, 경우의 수를 마킹해준다.

 

마킹의 순서는 다음과 같다.

 

1) 방문하지 않은 곳(-1인 곳)에 대하여 조건을 만족하는 좌표(현재보다 더 작은 값)로 이동하며 이동하였다는 의미로 0으로 마킹해준다.

 

2) 그러다가 목표지점 (n-1, m-1)에 도달하면 시작점에서 도착점까지 성공적으로 방문한 한 가지 경우가 되므로 1을 리턴해주고, 해당 값을 지금까지 걸어온 경로에 모두 더해준다.

 

3) 만약에 현재 방문중인 경로를 이미 다른 경로가 방문하여 -1이 아닌 다른 값으로 업데이트 되어있다면 (0 or n으로) 더 이상의 탐색은 진행하지 않고 해당 값을 업데이트 해준다. (만약 현재 방문한 좌표가 0이라고 한다면, 해당 경로로는 목표지점으로 도달할 수 없다는 뜻이고 n이라면 해당 경로를 통해 목표지점으로 가는 경우의 수를 지금까지 n개 찾았다는 것이다.)

 

이런식의 진행을 통해서 이미 알려진 경로에 대해서는 굳이 끝까지 탐색을 하지 않아 수행시간을 줄일 수 있다.