[백준] 17485 진우의 달 여행 (Large)

문제

• 지구와 달 사이를 NxM 행렬로 나타낼 때 우주선이 각 칸을 지날 때마다 소모해야할 연료가 기록되어 있다.
  • 2 <= N, M <= 1000
• 우주선의 특징은 다음과 같다.
  • 우주선은 왼쪽 아래, 아래, 오른쪽 아래 방향으로 이동할 수 있다.
  • 우주선은 같은 방향으로 두 번 연속 움직일 수 없다.
• 달에 도착하기 위한 최소 연료값은?

 

풀이 1

• 지구의 각 시작 위치에서의 최솟값을 구한 후 비교하기
• 처음에 DFS로 모든 경우의 수 비교하는 식으로 생각했는데, 그렇게 되면 대략 $2^{1000}$ 이니까 시간 초과다.
• memoization 이용해 시간 줄이기!
  • visited[a][b][d] :  d 방향으로 이동해 (a, b)에 도착한 경우 최소 연료값
  • d : 0 왼쪽 1 아래 2 오른쪽
• 풀고 나니까 DP 가 아닌가 싶다..

 

[ 주의 ]

• pypy로 해야 시간초과 안남
• setrecursionlimit 너무 높게 잡으면 메모리 초과 남
  • 생각없이 10**9 넣었다가 메모리 초과 떴다.

import sys
sys.setrecursionlimit(10**4)
INF = sys.maxsize
input = sys.stdin.readline

def dfs(x, y, d):
    if x == N :     # 도착한 경우
        return 0
    if visited[x][y][d] != INF :  # 이미 계산한 경우
        return visited[x][y][d]
    
    # 현재 방향을 제외한 두 가지 방향으로 이동
    for nd in [0, 1, 2]:
        # 이전 이동방향이 아니고 맵을 벗어나지 않으면, 이동
        if nd != d and 0 <= y+dir[nd] < M :
            next = dfs(x+1, y+dir[nd], nd) + graph[x][y]
            visited[x][y][d] = min(next, visited[x][y][d])
    
    return visited[x][y][d]

N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

answer = INF
visited = [[[INF]*3 for _ in range(M)] for _ in range(N)]
dir = [-1, 0, 1]        # 이동 방향
for col in range(M):    # 시작 지점
    for d in range(3):  # 3가지 방향으로 이동
        answer = min(answer, dfs(0, col, d))

print(answer)

 

풀이 2

• dp[i][j][d] : (i, j)까지 가는데 필요한 연료의 최솟값 (마지막 방향 d)
  • 왼쪽 방향에서 ( i, j)로 왔을 때는 (i-1, j+1)로부터 움직인 것이고
  • 위에서 ( i, j)로 왔을 때는 (i-1, j)로부터 움직인 것이고
  • 오른쪽 방향에서 ( i, j)로 왔을 때는 (i-1, j-1)로부터 움직인 것이다.
• 연속해서 움직이지 않는 경우 중 더 작은 값 + 현재 (i, j) 지나는데 필요한 연료 값을 더해 값을 갱신한다.

N, M = map(int, input().split())
spaces = [list(map(int, input().split())) for _ in range(N)]

# dp[i][j][d] : (i, j)까지 가는데 필요한 연료의 최솟값 (마지막 방향 d)
dp = [[[1e9]*3 for _ in range(M)] for _ in range(N)]
for col in range(M) :   # dp 초기화
    dp[0][col][-1] = dp[0][col][0] = dp[0][col][1] = spaces[0][col]

for row in range(1, N) :
    for col in range(M) :
        # 왼쪽 아래로 이동한 경우
        if col != M-1 :    
            dp[row][col][0] = min(dp[row-1][col+1][1], dp[row-1][col+1][2]) + spaces[row][col]
        # 바로 아래로 이동한 경우
        dp[row][col][1] = min(dp[row-1][col][0], dp[row-1][col][2]) + spaces[row][col]
        # 오른쪽 아래로 이동한 경우
        if col != 0 :
            dp[row][col][2] = min(dp[row-1][col-1][0], dp[row-1][col-1][1]) + spaces[row][col]

print(min([min(dp[N-1][col]) for col in range(M)]))

 

References

• 백준 17485
• 2023.04.29 오늘의 문제
• 백준 DP