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

문제 유형
dfs

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. n개의 같은 크기의 벽장들이 일렬로 붙어져 있고 벽장의 문은 n-2개만이 있다. 한 벽장 앞에 있는 문은 이웃 벽장 앞에 문이 없다면(즉, 벽장이 열려있다면) 그 벽장 앞으로 움직일 수 있다.
2. 풀어야 할 문제는 입력으로 주어지는 사용할 벽장의 순서에 따라서 벽장문을 이동하는 순서를 찾는 것이다. 이때 벽장문의 이동횟수를 최소로 하여야 한다. 입력은 다음과 같이 주어지며, 열려있는 벽장의 개수는 항상 2개이다.
3. 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들의 순서의 길이(최대 20), 그리고 그 다음줄부터 사용할 벽장의 번호가 한줄에 하나씩 순서대로 주어진다.

dfs를 통해서 해결할 수 있는 간단한 완전탐색 문제입니다.

만약 2번과 5번 문이 열려있고
3번 문을 열어야한다면 경우의 수는 두 가지 입니다.
1. 2번 문을 닫는 것
2. 5번 문을 닫는 것

2번문을 닫기 위해서는 3번문만 이동하면됩니다.
5번문을 닫기 위해서는 3번, 4번문을 이동해야합니다.

즉, 2번문을 닫으려면 1번 이동해야하고, 5번문을 닫으려면 2번 이동해야합니다.
-> 하지만, 현재의 최소 이동이 최종적으로 최적해를 보장하지 않기 때문에 2가지 경우 모두 탐색해줘야합니다.

static void dfs(int cur, int a, int b, int total) {

    if (cur == m) {

        min = Math.min(total, min);

        return;
    }

    dfs(cur + 1, order[cur], b, total + Math.abs(order[cur] - a));
    dfs(cur + 1, a, order[cur], total + Math.abs(order[cur] - b));
}

핵심 코드는 위와 같습니다.
사용할 벽장들의 개수가 최대 20개이기 때문에, 2^20으로 충분히 시간복잡도 내에 해결할 수 있습니다.

시간 복잡도
O(2^20)

코드

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


public class Main {
	
	static int n,m;
	static int min = Integer.MAX_VALUE;
	static int[] order;
	
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
       
        
        st = new StringTokenizer(br.readLine());
        
        m = Integer.parseInt(st.nextToken());
        
        order = new int[m];
        
        for (int i=0; i<m; i++) {
        	st = new StringTokenizer(br.readLine());
        	int num = Integer.parseInt(st.nextToken());
        	order[i] = num;
        }
        
        dfs(0, a, b, 0);
        
        System.out.println(min);

    }
    
    static void dfs(int cur, int a, int b, int total) {
    	
    	
    	if (cur == m) {
    		
    		min = Math.min(total, min);
    		
    		return;
    	}
    	
    	dfs(cur+1, order[cur], b, total + Math.abs(order[cur] - a));
    	dfs(cur+1, a, order[cur], total + Math.abs(order[cur] - b));
    }
    

}