1520: 내리막 길

풀이 시간

• 28m
• 처음에 dfs만을 이용해서 풀었는데, M과 N이 각각 최대 500이기 때문에 대충 한 칸씩 상하좌우를 탐색한다고 치면 시간 초과가 발생한다
• 알고리즘 분류를 보고 dp를 추가 이용해서 다시 풀었다

구현 방식

• dfs + dp 를 이용해서 풀었다

• 그냥 재귀를 돌면 시간초과가 나기 때문에 memoization을 이용해서 dp에 해당 좌표에서 끝점까지 가는 경로의 수가 저장되도록, 해당 좌표의 dp 값이 -1이 아닌 경우에는 탐색을 더 깊게 진행하지 않고 이를 반환해주도록 구현하였다
  
  

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

• 위와 같은 입력(문제의 예시와 같음)이 주어질 때, dp 테이블은 아래와 같은 순서로 완성된다

[[-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, 1, -1]]
[[-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1], [-1, -1, -1, 1, -1], [-1, -1, -1, 1, -1]]
[[-1, -1, -1, -1, -1], [-1, -1, -1, 1, -1], [-1, -1, -1, 1, -1], [-1, -1, -1, 1, -1]]
[[-1, -1, -1, -1, -1], [-1, -1, -1, 1, 1], [-1, -1, -1, 1, -1], [-1, -1, -1, 1, -1]]
[[-1, -1, -1, -1, 1], [-1, -1, -1, 1, 1], [-1, -1, -1, 1, -1], [-1, -1, -1, 1, -1]]
[[-1, -1, -1, 2, 1], [-1, -1, -1, 1, 1], [-1, -1, -1, 1, -1], [-1, -1, -1, 1, -1]]
[[-1, -1, 2, 2, 1], [-1, -1, -1, 1, 1], [-1, -1, -1, 1, -1], [-1, -1, -1, 1, -1]]
[[-1, 2, 2, 2, 1], [-1, -1, -1, 1, 1], [-1, -1, -1, 1, -1], [-1, -1, -1, 1, -1]]
[[-1, 2, 2, 2, 1], [-1, -1, -1, 1, 1], [-1, -1, -1, 1, -1], [-1, -1, 1, 1, -1]]
[[-1, 2, 2, 2, 1], [-1, -1, -1, 1, 1], [-1, -1, -1, 1, -1], [-1, 1, 1, 1, -1]]
[[-1, 2, 2, 2, 1], [-1, -1, -1, 1, 1], [-1, -1, -1, 1, -1], [1, 1, 1, 1, -1]]
[[-1, 2, 2, 2, 1], [-1, -1, -1, 1, 1], [1, -1, -1, 1, -1], [1, 1, 1, 1, -1]]
[[-1, 2, 2, 2, 1], [1, -1, -1, 1, 1], [1, -1, -1, 1, -1], [1, 1, 1, 1, -1]]
[[3, 2, 2, 2, 1], [1, -1, -1, 1, 1], [1, -1, -1, 1, -1], [1, 1, 1, 1, -1]] -> 최종 dp 테이블

시간초과 코드

import sys

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def dfs(x, y):
    global result

    if (x, y) == (M-1, N-1):
        result += 1
        return

    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]
        if 0 <= nx < M and 0 <= ny < N:
            if board[x][y] > board[nx][ny] and not visit[nx][ny]:
                visit[nx][ny] = True
                dfs(nx, ny)
                visit[nx][ny] = False
    

M, N = map(int, sys.stdin.readline()[:-1].split())
board = []
for m in range(M):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))

result = 0
visit = [[False] * N for _ in range(M)]
visit[0][0] = True
dfs(0, 0)
print(result)

• visit 리스트를 통해 중복 방문을 제거한다고 쳐도 백트래킹 방식이기 때문에 N, M이 각각 500이고 (0, 0)부터 (M-1, N-1)까지 가는 모든 경로가 내리막 길이라고하면 시간 복잡도가 (500 * 500) ^ 2 이기 때문에 시간초과가 발생한다

최종 코드

import sys

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def dfs(x, y):
    if (x, y) == (M-1, N-1):
        return 1

    if dp[x][y] != -1:
        return dp[x][y]

    cnt = 0
    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]
        if 0 <= nx < M and 0 <= ny < N:
            if board[x][y] > board[nx][ny]:
                cnt += dfs(nx, ny)
    dp[x][y] = cnt
    return dp[x][y]
    
M, N = map(int, sys.stdin.readline()[:-1].split())
board = []
for m in range(M):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))

dp = [[-1] * N for _ in range(M)]
print(dfs(0, 0))

결과

• 이런식으로 dfs + dp를 둘 다 사용하는 다른 문제도 풀어봐야겠다