백준 17484 - 진우의 달 여행(Small)

문제 설명

우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.

진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.

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

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

진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.

최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 지구부터 달까지 왼쪽 대각 아래, 아래, 오른쪽 대각 아래 방향으로만 이동하며 사용하는 연료의 최솟값을 구하는 것이다.

이때, 이전에 이동한 방향으로는 움직이지 못한다.

 

DFS, BFS 모두 가능하지만, DP를 이용하여 풀었다.

DP에서 기록할 것은 해당 칸에 도착하는 최소 비용이다.

DP 배열은 3차원 배열로 구성하였다.

해당 메모이제이션 배열을 이용하여 자신의 윗줄(지구와 가까운)에서 해당 칸까지 이동하는 최소 비용을 갱신하면 된다.

이때, 같은 방향은 무시하면 된다.

for (int i = 1; i < N; i++)
{
    for (int j = 0; j < M; j++)
    {
        for (int k = 0; k < 3; k++)
        {
            int fromY = i + dy[k];
            int fromX = j + dx[k];

            if (fromY < 0 || fromY >= N || fromX < 0 || fromX >= M) continue;

            for (int t = 0; t < 3; t++)
            {
                if (k == t) continue;

                if (dp[i][j][k] > dp[fromY][fromX][t] + Board[i][j])
                {
                    dp[i][j][k] = dp[fromY][fromX][t] + Board[i][j];
                }
            }
        }
    }
}

k는 현재 칸에서 윗칸으로 이동하는 방향이며, t는 위칸에 도착한 방향을 나타낸다.

즉, 빨간선은 k이며  파란 선과 초록선은 t가 된다.

이때, k는 오른쪽 대각으로 올라가기 때문에 같은 방향인 초록색 선은 무시해야 한다.

 

배열을 모두 채웠다면 마지막줄의 수 중 가장 작은 수를 고르면 된다.

int ans = INT_MAX;
for (int j = 0; j < M; j++)
{
    for (int k = 0; k < 3; k++)
    {
        ans = min(ans, dp[N - 1][j][k]);
    }
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, M;

vector<int> dy = { -1, -1, -1 };
vector<int> dx = { -1, 0, 1 };

const int MAX = 6 * 6 * 100 + 1;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    vector<vector<int>> Board(N, vector<int>(M, 0));
    int dp[7][7][3];
    fill(dp[0][0], dp[6][7], MAX);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> Board[i][j];
        }
    }

    for (int j = 0; j < M; j++)
    {
        for (int k = 0; k < 3; k++)
        {
            dp[0][j][k] = Board[0][j];
        }
    }

    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            for (int k = 0; k < 3; k++)
            {
                int fromY = i + dy[k];
                int fromX = j + dx[k];

                if (fromY < 0 || fromY >= N || fromX < 0 || fromX >= M) continue;

                for (int t = 0; t < 3; t++)
                {
                    if (k == t) continue;

                    if (dp[i][j][k] > dp[fromY][fromX][t] + Board[i][j])
                    {
                        dp[i][j][k] = dp[fromY][fromX][t] + Board[i][j];
                    }
                }
            }
        }
    }

    int ans = INT_MAX;
    for (int j = 0; j < M; j++)
    {
        for (int k = 0; k < 3; k++)
        {
            ans = min(ans, dp[N - 1][j][k]);
        }
    }

    cout << ans;

    return 0;
}

---