항해99 코테

[C++] 99클럽 코테 스터디 14일차 TIL + 진우의 달 여행 (Small) (백준 17484번)

탱도시락 2025. 4. 17. 19:38

✅ 오늘의 학습 키워드

  • 다이나믹 프로그래밍(DP)
  • 3차원 배열
  • 최소 비용 경로 탐색

✅ 공부한 내용

✔️ 문제 요약

(백준 문제 링크: https://www.acmicpc.net/problem/17484)

  • N x M 행렬에서 지구(첫 행)에서 달(마지막 행)까지 최소 연료로 이동하는 문제
  • 우주선은 세 가지 방향으로만 이동 가능:
    1. 왼쪽 대각선 아래 (↙)
    2. 바로 아래 (↓)
    3. 오른쪽 대각선 아래 (↘)

  • 제약 조건: 같은 방향으로 두 번 연속 이동할 수 없음
  • 지구의 어느 위치에서든 출발 가능, 달의 어느 위치든 착륙 가능

✔️ 풀이 로직

해당 문제는 다이나믹 프로그래밍(DP)을 통해 해결할 수 있다.
핵심 아이디어는 현재 위치와 이전 이동 방향을 함께 상태로 저장하는 점화식을 만드는 것이다.

1. 상태 정의

dp[i][j][k] = i행 j열에 도착했을 때, k 방향으로 왔을 때의 최소 연료량

여기서 k는 이동 방향을 의미한다.

  • k = 0: 왼쪽 대각선 아래로 이동
  • k = 1: 바로 아래로 이동
  • k = 2: 오른쪽 대각선 아래로 이동

2. 점화식 (이동)

각 위치에 대해 세 가지 방향으로 이동하는 경우를 계산한다.

 

이전 위치라는 것이 이해가 안될 수도 있기에 시각화를 해보았다.

   

     (i-1, j-1)  (i-1, j)  (i-1, j+1) - 이전 위치
              \          |           /
                \        |        /
     (k=0)  \       |      /  (k=2)
                      (k=1)

                     \   |   /
                      \  |  /
                       \ | /
                      (i, j) - 현재 위치
           

 

1. 왼쪽 대각선으로 도착한 경우 (k=0) -> j -1 에서 j로

dp[i][j][0] = min(dp[i-1][j-1][1], dp[i-1][j-1][2]) + space[i][j]
  • 이전 위치 (i-1, j-1)에서 바로 아래(1) 또는 오른쪽 대각선(2) 방향으로 이동한 경우 중 최솟값

2. 바로 아래로 도착한 경우 (k=1) -> j 에서 j로 

dp[i][j][1] = min(dp[i-1][j][0], dp[i-1][j][2]) + space[i][j]
  • 이전 위치 (i-1, j)에서 왼쪽 대각선(0) 또는 오른쪽 대각선(2) 방향으로 이동한 경우 중 최솟값

3. 오른쪽 대각선으로 도착한 경우 (k=2) -> j+1 에서 j로

dp[i][j][2] = min(dp[i-1][j+1][0], dp[i-1][j+1][1]) + space[i][j]
  • 이전 위치 (i-1, j+1)에서 왼쪽 대각선(0) 또는 바로 아래(1) 방향으로 이동한 경우 중 최솟값

3. 초기 상태 설정

dp[0][j][k] = space[0][j] (모든 j와 k에 대해)
  • 첫 번째 행의 모든 위치는 시작점이 될 수 있으므로, 해당 위치의 연료 값으로 초기화

4. 최종 결과 계산

oil = min(dp[N-1][j][k]) (모든 j와 k에 대해)
  • 마지막 행(달)의 모든 위치와 방향에 대해 최솟값 찾기.

✅ 오늘의 회고

- 😳 어떤 문제가 있었고, 나는 어떻게 해결을 했는지

처음에는 단순 그리디 알고리즘으로 접근하려고 했으나, "같은 방향으로 두 번 연속 이동할 수 없다"는 제약 때문에 단순히 현재 위치에서 최소 연료 값을 선택하는 방식으로는 전체 최적해를 구할 수 없다는 것을 깨달았다.

그래서 DP를 활용하되, 현재 상태를 단순히 (행, 열)로 정의하는 것이 아니라 (행, 열, 이전 이동 방향)으로 3차원 배열로 정의를 해야 했다. 이전 이동 방향을 저장해야 연속으로 같은 방향으로 이동하는 것을 방지할 수 있기 때문이다.

그래서 다음과 같이 3차원 DP 배열을 사용하는 방식으로 접근했다. (이 문제에서 조건이 M과 N은 최대 6까지이다.)

const int MAX_N = 6;
const int MAX_M = 6;

int dp[MAX_N][MAX_M][3];

여기서 세 번째 차원은 이전에 어떤 방향으로 이동해 왔는지를 나타낸다. 이를 통해 각 위치에 도달했을 때의 최소 연료량을 이전 방향에 따라 관리할 수 있다.

각 위치에서 세 가지 방향으로 이동할 때, 이전에 같은 방향으로 이동하지 않은 경우만 고려하여 점화식을 구성했다. 예를 들어, 현재 위치에서 왼쪽 대각선 아래로 이동하려면, 이전에 왼쪽 대각선 아래로 이동하지 않은 상태에서의 최솟값을 선택했다.

- 🤩 무엇을 새롭게 알았는지

항상 느끼는 것이지만 답을 알고 나면 쉽다..

✅ 전체 코드

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

const int MAX_N = 6;
const int MAX_M = 6;


int main(){
    int N, M;
    cin >> N >> M;

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

    // dp[i][j][k]: i행 j열에 도착했을 때, k방향으로 갔을때의 최소 연료
    int dp[MAX_N][MAX_M][3];

    // dp 배열 초기화
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            for(int k = 0; k < 3; k++){
                dp[i][j][k] = INT_MAX;
            }
        }
    }

    // 첫 번째 행 초기화
    for(int j = 0; j < M; j++){
        for(int k = 0; k < 3; k++){
            dp[0][j][k] = space[0][j];
        }
    }

    // dp 배열 채우기 -> 이동 수단
    for(int i = 1; i < N; i++){
        for(int j = 0; j < M; j++){

            //왼쪽 대각선 아래로 내려가는 경우 (j-1 -> j)
            if(j > 0) {
                dp[i][j][0] = min(dp[i-1][j-1][1], dp[i-1][j-1][2]) + space[i][j];
            }

            // 바로 아래로 내려가는 경우 (j -> j)
            dp[i][j][1] = min(dp[i-1][j][0], dp[i-1][j][2]) + space[i][j];

            // 오른쪽 대각선 아래로 내려가는 경우 (j+1 -> j)
            if(j < M-1){
                dp[i][j][2] = min(dp[i-1][j+1][0], dp[i-1][j+1][1]) + space[i][j];
            }
        }
    }

    // 마지막 행에서 최소값 찾기
    int oil = INT_MAX;
    for (int j = 0; j < M; j++) {
        for (int k = 0; k < 3; k++) {
            oil = min(oil, dp[N-1][j][k]);
        }
    }

    cout << oil << endl;

    return 0;
}