진우의 달 여행(Large)
문제 해석
- 지구에서 달로 가기 위해 소모해야하는 연료의 최솟값을 구하는 문제입니다.
- N x M 행렬에 각 원소의 값들은 해당 공간을 지날 때 소모하는 연료의 양입니다.
- 왼쪽아래, 아래, 오른쪽아래 각 3방향으로 이동할 수 있으며 연속된 방향으로 이동할 수 없습니다.
- 지구의 임의의 위치에서 출발하여 달 임의의 위치에 도착하면 됩니다.
설계(20)
- 처음에 이 문제를 보았을 때, 딱 dp문제인 것 같다는 느낌이 들었습니다. 이전의 값이 다음 이동할 때에도 사용되기 때문입니다.
- cache[x][y][이동방향]에 메모이제이션을 하여 각 방향에서 오는 연료의 합들의 최솟값들을 갱신시키도록 하였습니다.
- 또 다른 방법으로 다익스트라 알고리즘을 이용하여 문제를 해결할 수 있습니다.
- 이 또한 마찬가지로 dist배열에 각 이동방향에서 오는 연료의 합들의 최솟값들을 갱신시키면 됩니다.
구현(30)
코드1(dp)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 1002
#define INF 987654321
int map[MAXN][MAXN];
int cache[MAXN][MAXN][3];
int N, M;
int dp(int x, int y, int dir) {
int& ret = cache[x][y][dir];
if (ret != -1) return ret;
if (x == N) return ret = map[x][y];
ret = INF;
if (y - 1 >= 0 && dir != 0) ret = min(ret, dp(x + 1, y - 1, 0));
if (dir != 1) ret = min(ret, dp(x + 1, y, 1));
if (y + 1 < M && dir != 2) ret = min(ret, dp(x + 1, y + 1, 2));
return ret += map[x][y];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
memset(cache, -1, sizeof(cache));
for (int i = 1; i <= N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
}
}
int ans = INF;
for (int j = 0; j < M; j++) {
if (j - 1 >= 0) ans = min(ans, dp(1, j - 1, 0));
if (j + 1 < M) ans = min(ans,dp(1, j + 1, 2));
ans = min(ans,dp(1, j, 1));
}
cout << ans << "\n";
return 0;
}
코드2(dijkstra)
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 1000
#define INF 987654321
int map[MAXN][MAXN];
int dist[MAXN][MAXN][3];
int N, M;
struct node {
int x;
int y;
int weights;
int prev_dir;
bool operator < (const node a) const {
return a.weights < weights;
}
};
int dx[] = { 1,1,1 };
int dy[] = { -1,0,1 };
priority_queue<node> pq;
void dijkstra() {
while (!pq.empty()) {
int x = pq.top().x;
int y = pq.top().y;
int weights = pq.top().weights;
int prev_dir = pq.top().prev_dir;
pq.pop();
for (int k = 0; k < 3; k++) {
if (prev_dir == k) continue;
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
int next_weights = weights + map[nx][ny];
if (dist[nx][ny][k] > next_weights) {
dist[nx][ny][k] = next_weights;
pq.push({ nx,ny,next_weights,k });
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
for (int k = 0; k < 3; k++) {
dist[i][j][k] = INF;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
}
}
int ans = INF;
for (int j = 0; j < M; j++) {
if (j - 1 >= 0) {
pq.push({ 0,j - 1,map[0][j - 1],0 });
dist[0][j - 1][0] = 0;
}
if (j + 1 < M) {
pq.push({ 0,j + 1,map[0][j + 1],2 });
dist[0][j + 1][2] = 0;
}
pq.push({ 0,j,map[0][j],1 });
dist[0][j][1] = 0;
}
dijkstra();
for (int j = 0; j < M; j++) {
for (int k = 0; k < 3; k++) {
ans = min(ans, dist[N - 1][j][k]);
}
}
cout << ans << "\n";
return 0;
}
디버깅
- dp로 문제를 해결할 때, 2차원 배열로 이동방향에 상관없이 최솟값을 갱신시켜서 WA가 나왔습니다.
제출결과
144ms (dp)
384ms (dijkstra)
마무리
- dp 점화식을 짜는데 어려움이 있었습니다. bottom-up방식으로 짰으면 더욱 쉬웠을 것 같았습니다.