[BOJ] 17825. 주사위 윷놀이

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	static ArrayList<Integer>[] graph = new ArrayList[34];
	static HashMap<Integer,Integer> map = new HashMap<>();
	static int[] dice_numbers = new int[11];
	static int answer = 0;

	static boolean flag = false;
	public static void main(String[] args) {				
		int[] location = new int[4];
					
		boolean[] check = new boolean[34];
		
		Scanner sc = new Scanner(System.in);		
		
		for(int i = 0; i <= 9; i++) {
			dice_numbers[i] = sc.nextInt();
		}
						
		
		for(int i = 0; i < graph.length; i++) {
			graph[i] = new ArrayList<>();
		}
		
		map.put(0, 0);
		
		for(int i = 0; i < 20; i++) {
			graph[i].add(i+1);
			map.put(i+1,(i+1)*2);
		}
		
		graph[5].add(21);
		map.put(21, 13);
		graph[21].add(22);
		map.put(22, 16);
		graph[22].add(23);
		map.put(23, 19);
		graph[23].add(29);
		map.put(29, 25);
		graph[10].add(24);
		map.put(24,22);
		graph[24].add(25);
		map.put(25,24);
		graph[25].add(29);
		map.put(29,25);
		graph[15].add(26);
		map.put(26,28);
		graph[26].add(27);
		map.put(27,27);
		graph[27].add(28);
		map.put(28,26);
		graph[28].add(29);
		map.put(29,25);
		graph[29].add(30);
		map.put(30,30);
		graph[30].add(31);
		map.put(31,35);
		graph[31].add(20);		
		graph[20].add(33);
		map.put(33,0);
		
		solve(0, 0, dice_numbers[0], location, check, 0);
		
		System.out.println(answer);
		
	}	
	
	public static void solve(int index, int horse_number, int dice_number, int[] location, boolean[] check, int sum) {
		if(index >= 10) {			
			answer = Math.max(sum, answer);
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			if(location[i] == 33) continue;

			int current_position = location[i];
			int next_position = getNextPosition(location[i],dice_number);
			if(next_position!=33 && check[next_position]) continue;
			check[next_position] = true;			
			check[current_position] = false;			
			location[i] = next_position;
			solve(index+1, i, dice_numbers[index+1], location, check, sum + map.get(next_position));
			location[i] = current_position;			
			check[current_position] = true;
			check[next_position] = false;
		}		
	}
	
	public static int getNextPosition(int current_position, int dice_number) {
		boolean isSkip = false;		
		
		if(current_position == 5 || current_position == 10 || current_position == 15) isSkip = true;
		int next_position = 0;		
		for(int i = 0; i < dice_number; i++) {
			if(current_position == 33) return 33;
			
			if(isSkip) {
				next_position = graph[current_position].get(1);
				isSkip = false;
			} else {
				next_position = graph[current_position].get(0);
			}			
			current_position = next_position;			
		}				
		return next_position;
	}
}