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

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

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

엄청나게 실수한 부분을 못 찾아서 한참 헤맸다..

여기서는 2차원으로 단순히 다이나믹 프로그래밍을 하면 안되고 방향에 따라 비용에 차이가 생기므로 배열에 따라 추가적으로 다이나믹 프로그래밍을 하기 위해 3차원 배열을 써야한다.

 

→ total_cost[r][c][dir]

 

그리고 난 훨씬 공식을 알아보기 쉽도록 바텀업 스타일로 다이나믹 프로그래밍을 만들었다.

 

Double Free라고 처음보는 백준 에러가 떴었는데, 알고보니 초기 방향을 -1로 초기화했는데 이를 배열의 인덱스로 활용해버려서 에러가 떴었다. 그런데 평소와 달리 잘못된 접근으로 안 뜬 이유는 무엇이지..? -1로 배열의 이전 메모리를 접근해서 그런가..

그래서 -1인 경우에는 배열에 접근하지 않도록 한다.

 

그리고 이를 수정하고나서도 계속 틀렸다고만 떠서 답답했는데, 알고보니 리턴하는 값을 배열 값으로 해두어 방향이 -1인 경우에 초기화되지 않은 값이 리턴되는 경우가 있어서 틀렸던 것이었다. 그래서 이도 정정하니 제대로 통과되었다!

 

if(next_dir != -1) {
    total_cost[r][c][next_dir] = result;
}
return result;

 

그리고 다른 시중의 코드들을 보면 조건문으로 방향을 많이 처리하였던데, 그렇게 하면 작성해야할 코드도 늘어나고 실수를 할 가능성이 높아지기 때문에 최대한 패턴화하는 것이 좋다. 물론 이게 많은 시간이 소요된다면, 실전에서는 조건문으로 처리해도 좋지만 베스트는 아니라고 생각한다. 그래서 나는 아래와 같이 처리하였다.

 

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[r][c];
    result = min(result, sum_cost);
}

이후 방향과 동일해서는 안되고, 배열의 범위를 벗어나도 안된다.

가독성을 위해서는 continue 문은 간결하게 한 줄씩 적는 것이 좋다.

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

#define MAX_VALUE 1000001
#define MAX_SIZE 1001
using namespace std;

int N, M, answer = MAX_VALUE;
int dc[3] = {-1, 0, 1};
vector<vector<int>> cost(MAX_SIZE, vector<int>(MAX_SIZE, 0));
vector<vector<vector<int>>> total_cost(MAX_SIZE, vector<vector<int>>(MAX_SIZE, vector<int>(3, MAX_VALUE)));
int search(int r, int c, int next_dir) {
    if(r == 0) return cost[0][c];
    if(next_dir != -1 && total_cost[r][c][next_dir] < MAX_VALUE) 
        return total_cost[r][c][next_dir];
    int result = 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[r][c];
        result = min(result, sum_cost);
    }
    if(next_dir != -1) {
        total_cost[r][c][next_dir] = result;
    }
    return result;
}

int main() {
    cin >> N >> M;
    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++) {
        int value = search(N - 1, i, -1);
        answer = min(answer, value);
    }

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