[백준] 17484번: 진우의 달 여행(Small)

이 문제를 다이나믹 프로그래밍을 활용해 조금 더 난이도 있게 풀려면 풀 수 있으나, 기본적으로 N, M이 작기 때문에 다이나믹프로그래밍을 활용해 효율을 추구하지 않아도 되는 문제이다.

 

그리고 자칫 다이나믹프로그래밍을 잘못 활용했다가 왕창 틀려버렸다..ㅠㅡㅜ

아래 코드를 기반으로 다이나믹 프로그래밍을 수행하면 출발점에 따라 제한되는 방향이 생겨서 최소 비용이 달라진다.

따라서 다이나믹 프로그래밍으로 기록하지 않고 바로바로 검색하는 방향으로 했다.

 

그리고 다이나믹 프로그래밍 시에 주의해야할 점은, 최소 비용의 중복 가능성이다.

만약 A라는 방향과 B라는 방향에서 오는 값이 같다면 이 두 방향중 무얼 선택하느냐에 따라 이후의 방향 전개에 영향을 미치기 때문에 두 방향 모두 탐색해보기 위해 DP를 바텀업으로 접근하는 것을 추천한다. (DP에는 크게 탑다운, 바텀업이 있다.)그렇게 풀면 두 방향 모두 탐색해볼 수 있다.

 

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

#define MAX_VALUE 601
using namespace std;

int N, M, answer = MAX_VALUE;
int dc[3] = {-1, 0, 1};
int search(int r, int c, int next_dir, vector<vector<int>> &cost) {

    if(r == 0) return cost[0][c];
    int new_cost = MAX_VALUE;
    for(int d = 0;d < 3;d++) {
        if(d == next_dir) continue;
        if(c + dc[d] < 0 || c + dc[d] >= M) continue;
        int sum_cost = search(r - 1, c + dc[d], d, cost) + cost[r][c];
        new_cost = min(new_cost, sum_cost);
    }

    return new_cost;
}

int main() {
    cin >> N >> M;
    vector<vector<int>> cost(N, vector<int>(M, 0));
    for(int i = 0;i < N;i++) {
        for(int j = 0;j < M;j++) {
            cin >> cost[i][j];
        }
    }

    for(int i = 0;i < M;i++) {
        answer = min(answer, search(N - 1, i, -1, cost));
    }


    cout << answer << '\n';
}