[Algorithm] 백준 DP문제 - 벽장문의 이동(2666) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 벽장문의 이동 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2666

2666번: 벽장문의 이동

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main{
    static int n, m;
    static int[] arr;
    static int[][][] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int left = parseInt(st.nextToken()); // 왼쪽에 있는 포인터
        int right = parseInt(st.nextToken()); // 오른쪽에 있는 포인터
        
        m = parseInt(br.readLine());
        // dp[m][n][n] => m번째 움직어야 하는 방을 움직일 때, left와 right의 움직임 최소 값
        dp = new int[m][n + 1][n + 1]; // m은 이동 해야하는 개수, n + 1 : left 이동, n + 1: right 이동
        arr = new int[m]; // 움직어야 하는 방 저장
        for (int i = 0; i < m; i++) arr[i] = parseInt(br.readLine());
        
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) // (n은 1부터)
                Arrays.fill(dp[i][j], -1); // 초기 값은 -1로 초기화
        }
        
        System.out.println(dfs(0, left, right));
    }
    
    static int dfs(int idx, int left, int right) {
        if (idx == m) return 0; // 움직여야 하는 모든 움직임을 마친 경우
        
        if (dp[idx][left][right] == -1) { // 아직 dp가 업데이트 되지 않았음
            dp[idx][left][right] = Math.min(
                Math.abs(left - arr[idx]) + dfs(idx + 1, arr[idx], right), // left가 움직인 값 + 재귀로 다음 항, left가 움직여진 위치, right
                Math.abs(right - arr[idx]) + dfs(idx + 1, left, arr[idx])
            );
        }
        return dp[idx][left][right];
    }
}

 

2. 풀이 중점 사항

 

점화식 세우기

 

dp[m][left][right] 는 m번째 자리에 있는 방의 번호를 옮기는데 left방이 총 이동한 거리와 right 방이 총 이동한 거리를 더한 값의 최소를 DP로 정의하였습니다.

 

즉, 만약 m = 2, left = 3, right = 4라면, 현재 m의 방에서 left가 3에 위치해 있고 right가 4에 위치해 있는 상태까지 총거리의 최소를 의미하게 됩니다.

 

dp[idx][left][right] = Math.min(
	Math.abs(left - arr[idx]) + dfs(idx + 1, arr[idx], right),
    Math.abs(right - arr[idx]) + dfs(idx + 1, left, arr[idx])
)

이 점화식은 left - arr[idx] 즉 idx 번째에 옮겨야 하는 방의 위치에서 left를 뺀 후 절댓값을 취한 것이므로 이동 거리를 의미합니다.

그리고 arr[idx]는 현재 left를 움직였으므로 그 위치의 값을 넣어준 것입니다.

 

시나리오 

 

방 6개

m = 2

arr = {1, 4} 

left = 2, right  = 5 가 주어져 있다고 생각하겠습니다.

 

dp[0][2][5] = Math.min(

 

    Math.abs(left - arr[0]) + dfs(1, 1, 5)

    = Math.abs(2 - 1) + dfs(1, 1, 5)  = 1 +  dfs(1, 1, 5)

    = 1 + 

              dp[1][1][5] = Math.min(

                     

                  Math.abs(1 - arr[1]) + dfs(2, arr[1], 5) 

                  = Math.abs(1 - 4) + dfs(2, arr[1], 5) 

                  = 3 + dfs(2, 4, 5)

                  = 3 

                 , 

                 Math.abs(5 - arr[5]) + dfs(2, 1, arr[5])

                 = 1 + dfs(2, 1, 4)              

                 = 1 

                )

            =  1

            (dp[1][1][5] = 1 저장)

  = 1 + 1 = 2  

   , Math.abs(right - arr[0]) + dfs (1, 2, 1)

     = Math.abs(5 - 1) + dfs(1, 2, 1)

     =   4 + dfs(1, 2,  1) ~ 

 

 

이와 같은 재귀 형태로 반복이 진행됩니다.

따라서, 최솟값을 DFS 형태와 dp를 활용하여 구할 수 있습니다.

 

이상으로 벽장문의 이동 자바 풀이를 마치도록 하겠습니다. 감사합니다!!!