백준 17484 진우의 달 여행(Small) - JAVA

문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] space = new int[N][M];
        int[][][] dp = new int[N][M][3];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                space[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int j = 0; j < M; j++) {
            for (int dir = 0; dir < 3; dir++) {
                dp[0][j][dir] = space[0][j];
            }
        }
        int answer = 0;
        for (int j = 0; j < M; j++) {
            for (int dir = 0; dir < 3; dir++) {
                dp[0][j][dir] = space[0][j];
            }
        }
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (j == 0) {
                    // 이전 위치가 왼위대각에서 온 경우는 없으므로 매핑 X
                    dp[i][j][0] = Integer.MAX_VALUE;
                    // 이전 위치가 바로위 위치에서 온 경우 0번과 2번 가능
                    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + space[i][j];
                    // 이전 위치가 오른 위치에서 온 경우 1번과 2번 가능
                    dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + space[i][j];
                } else if (j == M - 1) {
                    dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + space[i][j];
                    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + space[i][j];
                    dp[i][j][2] = Integer.MAX_VALUE;
                } else {
                    // 왼쪽에서 온 값이므로 j - 1
                    dp[i][j][0] = Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + space[i][j];
                    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i - 1][j][2]) + space[i][j];
                    // 오른쪽에서 온 값이므로 j + 1
                    dp[i][j][2] = Math.min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + space[i][j];
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int j = 0; j < M; j++) {
            for (int dir = 0; dir < 3; dir++) {
                min = Math.min(min, dp[N - 1][j][dir]);
            }
        }
        bw.write(String.valueOf(min));
        bw.flush();
    }
}

 

알고리즘 설명

---

해당 문제에서 우주선은 위에서 아래로 이동하며, 이동 방향은 왼쪽 아래, 바로 아래, 오른쪽 아래 총 세 가지입니다.

단, 같은 방향을 연속으로 사용할 수 없습니다.

 

직관적으로 떠올릴 수 있는 방법은 DFS를 사용해 모든 경우의 수를 탐색하고, 각 경로에서 사용한 연료의 최솟값을 갱신하는 방식입니다.

 

실제로 이 문제의 입력 조건은 2 ≤ N, M ≤ 6으로 제한되어 있어 DFS로도 시간 초과가 발생하지 않을 수도 있습니다. 하지만 알고리즘의 시간복잡도 관점에서 보면 이야기가 달라집니다.

 

한 칸에서 이동할 수 있는 방향은 최대 3가지이므로, DFS의 시간복잡도는 O(3^(N - 1))라는 것을 알 수 있습니다. 이 경우, 만약 행의 개수가 20이라면, 모든 경우의 수는 10억 번 이상이 되어 현실적으로 매우 비효율적인 알고리즘이 됩니다.

 

이 문제의 핵심은 이전 선택이 다음 선택에 영향을 준다는 점입니다. 즉, 같은 칸이라도 어떤 방향으로 도착했는지에 따라 이후 선택이 달라집니다. 따라서 dp 배열은 dp[N][M][3]로 만들 수 있겠습니다.(dir은 이전 칸에서 현재 칸을 어떻게 왔는지 3가지: 왼쪽, 아래, 오른쪽)

 

먼저, dp의 첫번째 행은 이전 칸이 없기 때문에, 연료의 최솟값은 space[][] 배열의 첫번째 행과 같다고 할 수 있습니다.

 

이후에는, 현재 칸에 대해서 방향 별로 가능한 이전 칸을 확인하여 올 수 있는 3가지 이전 칸에 대해 최솟값을 입력해 줄 수 있겠습니다.

위의 그림에서도 볼 수 있듯이, 완전히 풀어 적어보면(제가 나중에 봤을 때 까먹지 않도록...)

1. dp[i][j][0]은 dp[i - 1][j -1][1] + space[i][j]와 dp[i - 1][j - 1][2] + space[i][j]중의 최소값
   -> 이미 "이전 칸의 이전 칸"에서 왼쪽 방향에서 왔으므로 아래(1)와 오른쪽(2) 중 최소값만을 비교
2. dp[i][j][1]은 dp[i - 1][j][0] + space[i][j]와 dp[i - 1][j][2] + space[i][j]중의 최소값
   -> 이미 "이전 칸의 이전 칸"에서 아래 방향에서 왔으므로 왼쪽(0)과 오른쪽(2) 중 최소값만을 비교
   
3. dp[i][j][2]는 dp[i - 1][j + 1][0] + space[i][j]와 dp[i - 1][j + 1][1] + space[i][j]중의 최소값
   -> 이미 "이전 칸의 이전 칸"에서 오른쪽 방향에서 왔으므로 왼쪽(0)와 아래(1) 중 최소값만을 비교
   

 

가장 왼쪽 칸은 이전 칸이 왼쪽일 수 없고, 가장 오른쪽 칸은 이전 칸이 오른쪽일 수 없다는 것에 유의하여 dp[][] 배열을 완성할 수 있겠습니다.

 

코드 해석

---

N × M 크기의 우주 공간(space)을 입력받고, dp[i][j][dir] 형태의 3차원 DP 배열을 생성합니다. dp배열의 첫 번째 행은 이전 칸이 존재하지 않으므로 어떤 방향으로 도착했든 해당 칸의 연료값 자체(space)가 최소값이 됩니다.

따라서, 모든 3방향에 대해 dp[0][j][dir] = space[0][j]를 입력해줍니다.

 

주어진 모든 칸에 대해 행과 열로 2중 for문을 돌리면서 칸이 존재하지 않아 올 수 없는 불가능한 방향에는 Integer.MAX_VALUE를 입력하여 불가능한 칸이 최소값이 되는 것을 방지하고, 이외의 칸에 대해서는 현재 방향과 연속되지 않는 이전 방향들만 비교하여 가능한 경로 중 최소값을 선택해 DP 값을 갱신합니다.

 

마지막으로, 마지막 행의 모든 칸에 대해 3가지 방향을 모두 비교하여 가장 작은 값을 출력합니다.