BOJ 17485

진우의 달 여행(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방식으로 짰으면 더욱 쉬웠을 것 같았습니다.