백준 2666 벽장문의 이동 (Java)

1. 문제 링크

2666번: 벽장문의 이동

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 열러 있는 두 곳의 위치와 사용 벽장 위치, 총 이동 횟수로 DFS 탐색을 진행한다.

2. 이동 횟수가 결과 보다 크다면 끝낸다.

3. 마지막 벽장까지 다 사용했다면 결과와 이동 횟수 중 작은 값을 결과로 저장한다.

4. 왼쪽 벽장을 사용 벽장으로 정한 경우와 왼쪽 벽장을 사용 벽장으로 정한 경우 각각으로 DFS 탐색을 진행한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int n, cmd, num[], result = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine()); //벽장 개수
		String[] split = br.readLine().split(" ");
		int one = Integer.parseInt(split[0]);
		int two = Integer.parseInt(split[1]); 
		cmd = Integer.parseInt(br.readLine()); //벽장 순서 길이
		num = new int[cmd];
		for(int i=0;i<cmd;i++) {
			num[i] = Integer.parseInt(br.readLine());
		} 
		
		dfs(one, two, 0, 0);
		
		System.out.println(result);
	}

	private static void dfs(int one, int two, int idx, int cnt) {
		if(cnt > result) {
			return;
		}
		
		if(idx == cmd) {
			result = Math.min(result, cnt);
			return;
		}
		
		//왼쪽
		dfs(num[idx], two, idx+1, cnt + Math.abs(one - num[idx]));
		
		//오른쪽
		dfs(one, num[idx], idx+1, cnt + Math.abs(two - num[idx]));
		
	}
}