백준 17484번: 진우의 달 여행 (Small) (C++)

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

17484번: 진우의 달 여행 (Small)

---

Solved By: DP (Recursive Call)

 

Bottom-Up 방식의 DP로 풀려했으나 지나온 방향을 중복적으로 선택하면 안 되는 것을 구현을 못 해서 Recursive Call의 형태로 코드를 짜야했습니다. 그러나, 짜기가 꽤 어려워 공부를 해보았습니다.

(https://oriburger.tistory.com/entry/PS%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-BOJ-17484-%EC%A7%84%EC%9A%B0%EC%9D%98-%EB%8B%AC-%EC%97%AC%ED%96%89Small?category=967352)

 

이 함수 또한 bottom-up의 방식으로 DFS의 형태를 하고 있습니다.

#include <iostream>
#define MAX 7
#define INF 1e9
using namespace std;

int arr[MAX][MAX];
int ans = INF;
int n, m;
int dx[3] = {-1, 0, 1};

int dfs(int y, int x, int last){
    if(y == n + 1) return 0;
    
    int ret = INF;
    for(int i = 0; i < 3; i++){
        if(last == i) continue;
        if(x + dx[i] <= 0 || x + dx[i] > m) continue;
        
        ret = min(ret, dfs(y + 1, x + dx[i], i) + arr[y][x]);
    }
    
    return ret;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> arr[i][j];
        }
    }
    
    for(int i = 1; i <= m; i++){
        ans = min(ans, dfs(1, i, -1));
    }
    
    cout << ans;
    return 0;
}