BOJ#2666 벽장문의 이동

BOJ#2666 벽장문의 이동

* 문제

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

* 풀이

1. 문제 이해

벽장문을 이동을 열려있는 문이 이동한다는 것으로 바꿔서 생각해봅시다. 훨씬 편하게 문제를 이해할 수 있습니다.

열려있는 문은 항상 2개 뿐이므로 하나를 F, 나머지를 S라고 해봅시다.

열려있는 문이 이동하므로 2가지 경우가 발생합니다. 

1) F가 이동하는 경우

2) S가 이동하는 경우

2. 풀이 설계

이 문제는 벽장문의 사용 순서에 따라 탐색이 진행되고, 완전 탐색이 되어야 합니다.

이 과정에서 필요한 것, 저장시켜야 하는 것, 변화하는 것들을 이용하여 dp를 정의하고 점화식을 세워보면

(정의)

dp[pos1][pos2][idx] : 열린문 F의 위치가 pos1이고 열린문 S의 위치가 pos2 그리고 현재 탐색 위치가 idx일 때, 벽장문을 모두 사용하는데 필요한 최소 이동의 수

(점화식)

dp[pos1][pos2][idx] = min(열린문 F가 이동하는 경우, 열린문 S가 이동하는 경우)

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%232666_DoorMove/src/Main.java

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

/**
 * BOJ#2666 벽장문의 이동
 * https://www.acmicpc.net/problem/2666
 */

public class Main {

    static int n; // 벽장의 개수
    static int m; // 사용할 벽장의 개수
    static int[] opened = new int[2];
    static int[] order;

    // dp[pos1][pos2][depth] : 열린문이 pos1, pos2에 위치하고 사용한 벽장문의 개수가 idx일때, 벽장문을 모두 사용하는데 필요한 최소 이동 수
    static int[][][] dp = new int[21][21][21];

    static final int NOT_VISITED = -1;

    static {

        for (int i = 0; i < 21; i++) {
            for (int j = 0; j < 21; j++) {

                Arrays.fill(dp[i][j], NOT_VISITED);
            }
        }
    }

    public static void main(String[] args) throws IOException {

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        opened[0] = Integer.parseInt(st.nextToken());
        opened[1] = Integer.parseInt(st.nextToken());

        m = Integer.parseInt(br.readLine());
        order = new int[m];
        for (int i = 0; i < m; i++) {

            order[i] = Integer.parseInt(br.readLine());
        }

        // solve
        System.out.println(solve(opened[0], opened[1], 0));
    }

    static int solve(int firstPos, int secondPos, int idx) {

        // 기저 조건
        if (idx == m) {

            return 0;
        }

        // memoization
        if (dp[firstPos][secondPos][idx] != NOT_VISITED) return dp[firstPos][secondPos][idx];

        // 탐색
        dp[firstPos][secondPos][idx] = Math.min(solve(order[idx], secondPos, idx + 1) + Math.abs((order[idx] - firstPos)),
                solve(firstPos, order[idx], idx + 1) + Math.abs((order[idx] - secondPos)));

        return dp[firstPos][secondPos][idx];
    }
}