백준 2666 (벽장문의 이동) - java

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

2666번: 벽장문의 이동

문제

n개의 같은 크기의 벽장들이 일렬로 붙어져 있고 벽장의 문은 n-2개만이 있다. 한 벽장 앞에 있는 문은 이웃 벽장 앞에 문이 없다면(즉, 벽장이 열려있다면) 그 벽장 앞으로 움직일 수 있다.

그림은 7개의 벽장의 예이다. 그림에서 2번 벽장과 5번 벽장이 열려있고, 나머지 벽장은 닫혀 있다.  벽장 문은 좌우 어느 쪽이든 그 이웃 벽장이 열려 있다면 그 쪽으로 한 칸씩 이동할 수 있다. 그림에서 주어진 상태에서는 1번 벽장을 닫고 있는 벽장문을 오른쪽으로 한 칸 이동함으로써 1번 벽장을 사용할 수 있다. 이때 2번 벽장은 닫혀져 사용할 수 없다. 역시 5번 벽장이 열려 있으므로 4번 벽장 또는 6번 벽장 앞의 벽장문을 5번 벽장 앞으로 이동시킬 수 있다.

풀어야 할 문제는 입력으로 주어지는 사용할 벽장의 순서에 따라서 벽장문을 이동하는 순서를 찾는 것이다. 이때 벽장문의 이동횟수를 최소로 하여야 한다. 입력은 다음과 같이 주어지며, 열려있는 벽장의 개수는 항상 2개이다.

예를 들어 사용할 벽장 순서가 3 1 6 5이면, 3번 앞의 문을 2번으로 옮겨서 3번 벽장을 사용하고(문 이동횟수=1), 다음에 1번과 2번 앞에 있는 문을 오른쪽으로 하나씩 옮겨서(문 이동횟수=2) 1번 벽장을 사용하며, 6번 앞에 있는 문을 왼쪽으로 옮겨서 6번 벽장을 사용하고(문 이동횟수=1), 다시 그 문을 오른쪽으로 옮겨서 5번 벽장을 사용한다(문 이동횟수=1), 따라서 문이 이동한 횟수의 합은 5이다.

 

유형 : DP 

 

접근 방식

• 3차원 DP이다.
  • dp[i][j][k]에 대해 i번째 순서에 대해 j와 k의 문을 열었을 때 최소 문을 연 횟수를 저장한다.
  • 0번째 순서에 열려있는 두 문에 대해 0으로 초기화한다.
• i번째 순서에 열어야 할 문을 curNum이라 칭하겠다. 그리고 열려있는 두 문에 대해 작은 숫자(왼쪽)문을 minNum , 큰 숫자(오른쪽)문을 maxNum이라 칭하겠다.
• 위와 같은 상황에서 우리는 4가지 상황을 고려하면된다.
  • 해당 문이 이미 열려 있는 경우
    • 문을 건드리지 않아도 된다.
  • curNum이 minNum보다 작은 경우
    • minNum을 curNum으로 이동시켜야 한다.
  • curNum이 minNum보다 크지만 maxNum보다 작은 경우
    • minNum을 curNum으로 이동시키는 경우
    • maxNum을 curNum으로 이동시키는 경우
  • curNum이 maxNum보다 큰 경우
    • maxNum을 curNum으로 이동시키는 경우

전체 코드

package DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2666_벽장문의_이동 {

    static int n = 0;
    static int m = 0;

    static int open1,open2;

    static int[] use;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()," ");
        open1 = Integer.parseInt(st.nextToken());
        open2 = Integer.parseInt(st.nextToken());


        st = new StringTokenizer(br.readLine()," ");
        m = Integer.parseInt(st.nextToken());

        use = new int[m+1];

        for(int i=1 ; i<= m ; i++){
            use[i] = Integer.parseInt(br.readLine());
        }

        int[][][] dp = new int[21][n+1][n+1];

        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    dp[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }

        dp[0][open1][open2] = 0;
        dp[0][open2][open1] = 0;

        // dp[i][j][k] : i번째 차례에 j와 k문이 열려있을 때 최소 이동 횟수

        int result = Integer.MAX_VALUE;

        for(int k=1; k<=m; k++){
            int curUse = use[k]; // 열어야 할 문

            for(int i=1 ; i<=n ; i++){
                for(int j=1 ;j<=n ; j++) {

                    if (dp[k - 1][i][j] == Integer.MAX_VALUE)
                        continue; // 이전에 열린적이 없으면 pass

                    int minNum = Math.min(i, j);
                    int maxNum = Math.max(i, j); // 작은값과 큰값

                    // 해당 차례의 문이 이미 열려있다면
                    if (curUse == minNum || curUse == maxNum) {
                        dp[k][minNum][maxNum] = Math.min(dp[k][minNum][maxNum], dp[k - 1][i][j]);

                        if (k == m) {
                            result = Math.min(result, dp[k][minNum][maxNum]);
                        }

                        continue;
                    }

                    // 작은 번호의 문보다 앞쪽에 있다면
                    if (curUse < minNum) {
                        dp[k][curUse][maxNum] = Math.min(dp[k][curUse][maxNum], dp[k - 1][i][j] + Math.abs(curUse - minNum));

                        if (k == m) {
                            result = Math.min(result, dp[k][curUse][maxNum]);
                        }

                    }

                    // 큰 번호의 문보다 오른쪽에 있다면
                    else if(maxNum < curUse){
                        dp[k][minNum][curUse] = Math.min(dp[k][minNum][curUse],dp[k-1][i][j] + Math.abs(curUse - maxNum));

                        if(k == m){
                            result = Math.min(result,dp[k][minNum][curUse]);
                        }
                    }

                    // 열려있는 두 문 사이에 있다면
                    else {

                        dp[k][minNum][curUse] = Math.min(dp[k][minNum][curUse], dp[k - 1][i][j] + Math.abs(curUse - maxNum));
                        dp[k][curUse][maxNum] = Math.min(dp[k][curUse][maxNum], dp[k - 1][i][j] + Math.abs(curUse - minNum));

                        if (k == m) {
                            result = Math.min(result, Math.min(dp[k][minNum][curUse], dp[k][curUse][maxNum]));
                        }
                    }
                }
            }
        }

        System.out.println(result);
        br.close();
    }

}