https://www.acmicpc.net/problem/17484
난이도
실버3
문제
우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.
진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.
-
지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.
-
우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.
진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.
최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.
입력
첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다.
다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.
출력
달 여행에 필요한 최소 연료의 값을 출력한다.
내 코드
DFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
static int N, M;
static int[][] map;
static int ans = Integer.MAX_VALUE;
static int[] dir = {-1, 0, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i = 0; i < M; i++){
dfs(0, i, -1, map[0][i]);
}
System.out.println(ans);
}
public static void dfs(int r, int c, int predir, int tmpAns){
if(r == N-1){
ans = Math.min(ans, tmpAns);
return;
}
for(int i = 0; i < 3; i++){
int nc = c + dir[i];
if(nc >= 0 && nc < M && predir != i){
dfs(r+1, nc, i, tmpAns + map[r+1][nc]);
}
}
}
}문제를 읽고 DP인 것 같았는데, 같은 방향으로 두번 연속 이동할 수 없다는 문구를 보고
어떻게 점화식을 세워야할지 감이 오지 않았다...
그래서 그냥 DFS로 풀어봤는데 생각보다 오래 걸리지도 않았고, 정답도 잘 맞았다.
DFS로 코드를 작성하면서 같은 이전 방향을 계속해서 들고 다니면서,
이전 방향과 일치하지 않는 경우에만 더 나아가도록 코드를 작성했다.
DP
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
int[][] map = new int[n][m];
int[][][] dp = new int[n][m][3];
for(int i = 0; i < n; i++) {
s = br.readLine().split(" ");
for(int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(s[j]);
Arrays.fill(dp[i][j], (int)1e9);
}
}
for(int j = 0; j < m; j++) {
for(int k = 0; k < 3; k++){
dp[0][j][k] = map[0][j];
}
}
for(int i = 1; i < n; i++) {
for(int j = 0; j < m; j++) {
if(j == 0) {
dp[i][j][0] = Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + map[i][j];
dp[i][j][1] = dp[i - 1][j][0] + map[i][j];
} else if(j == m - 1) {
dp[i][j][2] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0]) + map[i][j];
dp[i][j][1] = dp[i - 1][j][2] + map[i][j];
} else {
dp[i][j][0] = Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + map[i][j];
dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + map[i][j];
dp[i][j][2] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0]) + map[i][j];
}
}
}
int min = Integer.MAX_VALUE;
for(int j = 0; j < m; j++) {
for (int i = 0; i < 3; i++) {
min = Math.min(min, dp[n - 1][j][i]);
}
}
System.out.println(min);
}
}범위가 작아서 그런지 실행 시간이나 메모리 측면에서 크게 다르지 않다.
3차원 배열을 거의 사용해보지 않아서 다른 사람들의 코드를 참고 하였다.
dp[i][j][숫자] 에서 숫자가 의미하는 것은
0은 오른쪽 아래로 이동
1은 바로 아래로 이동
2는 왼쪽 아래로 이동이다.
dp[i][j][0] = Math.min(dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]) + map[i][j];
dp[i][j][1] = dp[i - 1][j][0] + map[i][j];j == 0 일 때, 왼쪽으로는 더 이동이 불가하기 때문에
0(오른쪽 아래로 이동)과 1(바로 아래로 이동)만 업데이트를 해준다.
dp[i][j][2] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0]) + map[i][j];
dp[i][j][1] = dp[i - 1][j][2] + map[i][j];j == m-1 일 때, 오른쪽으로는 더 이동이 불가하기 때문에
2(왼쪽 아래로 이동)과 1(바로 아래로 이동)만 업데이트를 해준다.
그 외에는 0, 1, 2를 모두 업데이트 하면서 dp를 채워나가고,
최소값을 출력하면 된다.
