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

문제링크 : https://www.acmicpc.net/problem/17485

17485번: 진우의 달 여행 (Large)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, arr[1001][1001], dp[1001][1001][3]; //직전 방향 체크

int func(int y, int x, int dir)
{   
    if(y > N || y < 1 || x > M || x < 1) return MAX;
    if(dp[y][x][dir] != MAX) return dp[y][x][dir];

    if(dir == 0) dp[y][x][dir] = arr[y][x] + min(func(y-1, x, 1), func(y-1, x+1, 2));
    else if(dir == 1) dp[y][x][dir] = arr[y][x] + min(func(y-1, x-1, 0), func(y-1, x+1, 2));
    else if(dir == 2) dp[y][x][dir] = arr[y][x] + min(func(y-1, x-1, 0), func(y-1, x, 1));
    return dp[y][x][dir];
}

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

    cin >> N >> M;

    
    for(int i=0; i<1001; i++)
    {
        for(int j=0; j< 1001; j++)
        {
            for(int k=0; k<3; k++) 
            {
                dp[i][j][k] = MAX;
            }
        }
    }

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            cin >> arr[i][j];
            if(i==1) //첫째 줄 초기화
            {
                dp[i][j][0] = arr[i][j];
                dp[i][j][1] = arr[i][j];
                dp[i][j][2] = arr[i][j];   
            }
        }
    }
    
    int result = MAX;
    for(int i=1; i<=M; i++)
    {
        for(int j=0; j<3; j++)
        {
            result = min(result, func(N, i, j)); //마지막 줄에서 가장 작은 값 저장
        }
    }

    cout << result;

    return 0;
}

직전 위치 뿐만 아니라 같은 방향이 유지되면 안되므로 방향 또한 체크를 해주어야 한다.

방향은 다음과 같이 정하였다.

0 = ↙
1 = ↓
2 = ↘

 

달에 도달하기 위해서는 마지막 행에 도달하여야 한다.

따라서 우리가 구하고자하는 값은 마지막 행에서의 최소값이며, 이는 재귀를 통해 직전 방향을 거슬러 올라가며 찾아가게 된다.

방향에 따라 거슬러 올라가다보면 첫째 행에 도달하게 되며, 따라서 첫째 행의 dp을 해당 칸의 arr 배열 값으로 초기화해주어야 한다.

이외의 범위는 최솟값 판별을 위해 MAX로 초기화해준다.

 

현재 방향에 따라 가능한 직전 방향 2가지로 거슬러 올라가며, 둘 중 더 작은 값을 가진 것을 반환한다.

↙의 경우에는 직전 방향으로 ↓과 ↘이 가능하며,

↓의 경우에는 직전 방향으로 ↙과 ↘이 가능하며,

↘의 경우에는 직전 방향으로 ↓과 ↙아 가능하다,

 

↙는 아래로 한칸, 좌로 한칸이므로 직전 위치는 y-1, x-1이며,

↓는 아래로 한칸만 이동이므로 직전 위치는 y-1, x이며,

↘는 아래로 한칸, 우로 한칸이므로 직전 위치는 y-1, x+1이다.

 

위 내용을 조합하여 현재 방향에 따라 직전 방향에서의 값을 가져와 최솟값을 반환해준다.

재귀를 돌면서 이미 방문했던 지역에 또 방문한 경우는 중복이기에 이미 값이 있다면 바로 반환해주도록 하고, y와 x의 값이 방향에 따라 이동하면서 범위 밖에 나가지 않도록 체크도 필요하다. (0<x<M, 0<y<N)

 

재귀 탐색을 마치고 앞서 설명했던 대로 마지막 행에 도달하여야 달로 갈 수 있으므로, 가장 적은 비용을 위해 마지막 행에서의 가장 작은 값을 저장하여 출력해준다.