[Java] 백준 2666번 : 벽장문의 이동

1. 문제

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

2666번: 벽장문의 이동

 

 

2. 풀이 과정

방법 1. DFS

열어야 하는 문이 왼쪽 열린 문과 오른쪽 열린 문 사이에 있다면, 깊이 우선 탐색으로 둘 다 탐색해본다.

열어야 하는 문이 두 개의 열린 문보다 왼쪽에 있다면, 왼쪽 열린 문을 당겨와서 사용한다.

열어야 하는 문이 두 개의 열린 문보다 오른쪽에 있다면, 오른쪽 열린 문을 당겨와서 사용한다.

이때, 현재까지 구한 결과 값보다 중간 값이 이미 크다면 더이상 탐색할 수 없으므로 넘어간다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int N, M, result;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] opened = br.readLine().split(" ");
        int left = Integer.parseInt(opened[0]);
        int right = Integer.parseInt(opened[1]);

        M = Integer.parseInt(br.readLine());
        arr = new int[M];
        for(int i = 0; i < M; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        result = Integer.MAX_VALUE;
        dfs(0, left, right, 0);
        System.out.println(result);
    }

    public static void dfs(int idx, int l, int r, int sum){
        if(result <= sum){
            return;
        }
        if(idx == M){
            result = sum;
            return;
        }

        if(l==arr[idx] || r == arr[idx]){
            dfs(idx+1, l, r, sum);
        }
        else if(l < arr[idx] && arr[idx] < r){
            dfs(idx+1, arr[idx], r, sum + arr[idx] - l);
            dfs(idx+1, l, arr[idx], sum + r - arr[idx]);
        }
        else if(arr[idx] < l){
            dfs(idx+1, arr[idx], r, sum + l - arr[idx]);
        }
        else {
            dfs(idx+1, l, arr[idx], sum + arr[idx] - r);
        }
    }

}

 

결과

 

방법 2. DP + DFS

[지금열어야할 벽장문의 인덱스 값][왼쪽의 열린 문][오른쪽의 열린 문]으로 3차원 배열을 생성한 후, 깊이 우선 탐색을 통해 해당 상태에서 최종까지 고려했을 때의 최소값을 업데이트한다.

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

public class Main {
    static int N, M;
    static int[] arr;
    static int[][][] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] opened = br.readLine().split(" ");
        int left = Integer.parseInt(opened[0]);
        int right = Integer.parseInt(opened[1]);

        M = Integer.parseInt(br.readLine());
        dp = new int[M][N + 1][N + 1];
        arr = new int[M];
        for(int i = 0; i < M; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        for(int i = 0; i < M; i++){
            for(int j = 1; j <= N; j++){
                Arrays.fill(dp[i][j], -1);
            }
        }

        System.out.println(solve(0, left, right));
    }

    public static int solve(int idx, int l, int r){
        if(idx == M){
            return 0;
        }

        if(dp[idx][l][r] == -1){
            dp[idx][l][r] = Math.min(
                    Math.abs(l - arr[idx]) + solve(idx + 1, arr[idx], r),
                    Math.abs(r - arr[idx]) + solve(idx + 1, l, arr[idx])
            );
        }

        return dp[idx][l][r];
    }

}

 

결과