정올 JAVA - 벽장문의 이동 (1409) 백트래킹

https://beta.jungol.co.kr/problem/1409?cursor=eyJwcm9ibGVtc2V0Ijo4LCJmaWVsZCI6MiwiaWR4Ijo1fQ==

 

1. rec(열어야할 벽장 위치, 비용(현재 벽장 위치 - 열려있는 벽장 위치), 열린 곳01, 열린 곳 02)

2. 비용이 구해놓은 최솟값보다 크면 더이상 탐색하지 않고 돌아간다.

 

 

import java.util.Scanner;
import java.util.ArrayList;
public class Main {
	static int n;
	static int open1, open2;
	static int go;
	static int answer = 0x7fffffff;
	static ArrayList<Integer> arr = new ArrayList<Integer>();
	
	static void rec(int cnt, int cost, int Open1, int Open2) {
		if(answer < cost) return; // 비용이 구해놓은 최솟값보다 크면 리턴
        
		if(cnt == go) {
			answer = cost;
			return;
		}
		
		
		if(arr.get(cnt) == Open1 || arr.get(cnt) == Open2) { // 현재 위치에 벽장문이 열려있으면 바로 다음 벽장으로
			rec(cnt + 1, cost, Open1, Open2);
		}else {
			rec(cnt + 1, cost + Math.abs(arr.get(cnt) - Open1), arr.get(cnt), Open2);
			rec(cnt + 1, cost + Math.abs(Open2 - arr.get(cnt)), Open1 ,arr.get(cnt));			
		}
		
		return;
	}
	
	
	public static void main(String agus[]) {
		Scanner input = new Scanner(System.in);
		
		n = input.nextInt();
		open1 = input.nextInt();
		open2 = input.nextInt();
		go = input.nextInt();

		
		for(int i = 0 ; i < go ; i++) 
			arr.add(input.nextInt());
		
			
		rec(0, 0, open1, open2);
		System.out.println(answer);
	}
}