[백준/C++] 17485번: 진우의 달 여행 (Large)

문제

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

---

문제 요약

 지구에서 달 사이의 공간을 지날 때 소모되는 연료 양을 나타내는 n × m 배열이 주어진다.

 

 

지구에서 달로 가는 경우, 우주선이 움직일 수 있는 방향은 아래와 같다.

 

또한, 우주선은 전에 움직인 방향으로 움직일 수 없다. (같은 방향으로 두 번 연속 움직일 수 없다.)

 

달에 도달하기 위한 연료의 최솟값을 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int n, m;

int board[1010][1010];

// dp[i][j][k]: (x, y)부터 끝까지 이동했을 때의 최소 비용 
// (왼쪽, 가운데, 오른쪽에서 올경우, 시작점)
int dp[1010][1010][4];

int dfs(int x, int y, int d) {
    if (x == n) {
        return 0;
    }

    if (dp[x][y][d] != 1e9) {
        return dp[x][y][d];
    }

    // 마지막으로 가운데 또는 오른쪽으로 이동했을 경우
    if (d != 0 && y - 1 >= 0) {
        // 왼쪽으로 이동할 경우 탐색
        dp[x][y][d] = dfs(x + 1, y - 1, 0) + board[x][y];
    }

    // 마지막으로 왼쪽 또는 오른쪽으로 이동했을 경우
    if (d != 1) {
        // 가운데로 이동할 경우 탐색
        dp[x][y][d] = min(dp[x][y][d], dfs(x + 1, y, 1) + board[x][y]);
    }

    // 마지막으로 가운데 또는 왼쪽으로 이동했을 경우
    if (d != 2 && y + 1 < m) {
        // 오른쪽으로 이동할 경우 탐색
        dp[x][y][d] = min(dp[x][y][d], dfs(x + 1, y + 1, 2) + board[x][y]);
    }

    return dp[x][y][d];
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];

            // dp 배열 초기화
            for (int k = 0; k < 4; k++) {
                dp[i][j][k] = 1e9;
            }
        }
    }

    int res = 1e9;

    for (int i = 0; i < m; i++) {
        res = min(res, dfs(0, i, 3));
    }
    
    cout << res;

    return 0;
}

---

코드 설명

3차원 Top Down Dynamic Programming을 이용한다.

dfs(x, y, d) = dp[x][y][d]
=> (x, y)부터 끝까지 이동했을 때의 최소 비용(d = 3인 경우, 출발 지점을 나타낸다.)

 

1. 지구와 달 사이에 공간을 나타내는 행렬을 2차원 배열에 저장한다.

 

2. m개의 출발 지점에서 dfs()를 진행한다.

 

2 - 1. 우주선이 끝에 도달했으면 0을 반환하여 이동을 종료한다.

 

2 - 2. dfs(x, y, d) 값이 이미 dp 배열에 저장되어 있는 경우, 추가적인 연산 없이 바로 dp[i][j][d]를 반환한다.

 

2 - 3. 현재 이동 방향을 고려하여, 해당 방향을 제외한 방향으로 DFS 탐색을 진행한다.

(배열의 인덱스를 벗어나지 않도록 현재 y좌표도 고려해야 한다.)

 

3. 탐색한 결과의 최솟값을 출력한다.