진우의 달 여행(Large)

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

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

 

 

#include<iostream>
#include<queue>
 
using namespace std;
 
int n, m;
int map[1002][1000];
int dist[1002][1000];
int d[1002][1000][3];
int dx[] = { 1,1,1 };
int dy[] = { 1,0,-1 };
int ans = 987654321;
 
void dp() {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 3; j++) {
            d[0][i][j] = map[0][i];
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j == 0) {
                d[i][j][1] = d[i - 1][j + 1][0] + map[i][j];
                d[i][j][2] = min(d[i - 1][j][1], d[i - 1][j + 1][0]) + map[i][j];
            }
            else if (j == m - 1) {
                d[i][j][0] = min(d[i - 1][j][1], d[i - 1][j - 1][2]) + map[i][j];
                d[i][j][1] = d[i - 1][j - 1][2] + map[i][j];
            }
            else {
                d[i][j][0] = min(d[i - 1][j - 1][2], d[i - 1][j][1]) + map[i][j];
                d[i][j][1] = min(d[i - 1][j - 1][2], d[i - 1][j + 1][0]) + map[i][j];
                d[i][j][2] = min(d[i - 1][j][1], d[i - 1][j + 1][0]) + map[i][j];
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 3; j++) {
            if (d[n - 1][i][j] < ans && d[n - 1][i][j] != 0) ans = d[n - 1][i][j];
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    //bfs();
    dp();
 
    cout << ans << '\n';
    return 0;
}
 

DP문제, 처음에는 다익스트라비슷한 BFS생각을했는데,

크기가 1000*1000에서 중복발생이 많다면 분명히 시간초과가 나는것을 예상했다

BFS는 지양하고, DP점화식을세우는과정에서, 이전에 풀었던 RGB거리가 생각났던문제다.

점화식 세우는게 어렵지 않은문제 시간을 더줄일수있을진모르겠다.