[백준/자바] 17825 주사위 윷놀이

사진 클릭시 문제로 이동

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1

1 2 3 4 1 2 3 4 1 2

예제 출력 1 

190

예제 입력 2 

1 1 1 1 1 1 1 1 1 1

예제 출력 2 

133

예제 입력 3 

5 1 2 3 4 5 5 3 2 4

예제 출력 3 

214

예제 입력 4 

5 5 5 5 5 5 5 5 5 5

예제 출력 4 

130

---

설명

백트래킹을 이용한 문제다.

 

다음과 같은 번호를 가지는 배열을 만든다.

static int map[][] = {{0, 2, 4, 6, 8, 10}, {10, 13, 16, 19, 25}, {10, 12, 14, 16, 18, 20}, {20, 22, 24, 25}, {20, 22, 24, 26, 28, 30}, {30, 28, 27, 26, 25}, {30, 32, 34, 36, 38, 40}, {25, 30, 35, 40}, {40, 0}};

잘 보면 짝수 화살표의 경우 파란 칸 즉 해당 배열 인덱스의 끝에 도달하면 짝수 +1의 인덱스로 이동하는 것을 알 수 있다. 

예외적으로 6번은 8번 화살표로 이동한다.

홀수 화살표의 경우 모두 7번 화살표로 이동한다.

예외적으로 7번은 8번 화살표로 이동한다.

 

배열의 인덱스보다 더 많이 간다면,

짝수 화살표의 경우 +2한 짝수 화살표를 따라가는 것을 확인할 수 있다.

홀수 화살표의 경우 7번 화살표로 이동하지만 7번 화살표의 길이가 4인 것을 통해 7번을 넘어 8번 화살표까지 도달할 수 있다는 전제를 해서 문제를 풀어야 한다.

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class BOJ17825 {
	static int score = 0;
	static int map[][] = {{0, 2, 4, 6, 8, 10}, {10, 13, 16, 19, 25}, {10, 12, 14, 16, 18, 20}, {20, 22, 24, 25}, {20, 22, 24, 26, 28, 30}, {30, 28, 27, 26, 25}, {30, 32, 34, 36, 38, 40}, {25, 30, 35, 40}, {40, 0}};
	static int play[] = new int[10];
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	boolean visited[][] = {{false, false, false, false, false, false}, {false, false, false, false, false}, {false, false, false, false, false, false}, {false, false, false, false}, {false, false, false, false, false, false}, {false, false, false, false, false}, {false, false, false, false, false,false}, {false, false, false, false}, {false, false}};
	int yut[][] = {{0,0},{0,0},{0,0},{0,0}};
	for(int i = 0; i < 10; i++) {
	play[i] = Integer.parseInt(st.nextToken());
	}
	game(0, yut, 0, visited);
	System.out.println(score);
	}
	static void game(int ind, int[][] y, int s, boolean visited[][]) {
	if(ind >= 10) {
	score = Math.max(score, s);
	return;
	}
	for(int i = 0; i < 4; i++) {
	if(y[i][0] == 8 && y[i][1] == 1) continue;
	int sr = y[i][0];
	int sc = y[i][1];
	int cr = y[i][0];
	int cc = y[i][1] + play[ind];
	if(cc == map[cr].length-1) {
	if(cr < 6 && cr%2 == 0) { // 0 -> 1, 2 -> 3, 4 -> 5
	cr++;
	cc = 0;
	}else if(cr == 6 || cr == 7) { // 6, 7 -> 8
	cr = 8;
	cc = 0;
	}else if(cr%2 == 1){ // 1, 3, 5 -> 7
	cr = 7;
	cc = 0;
	}else {
	cc = 1;
	}
	}else if(cc >= map[cr].length) {
	cc = cc - map[cr].length + 1;
	if(cr%2 == 0) { // 0 -> 2, 2 -> 4, 4 -> 6, 6 -> 8, 8 -> 스탑
	cr += 2;
	if(cr >= 8) {
	cr = 8;
	if(cc >= 1) {
	cc = 1;
	}
	}
	}else if(cr == 7) {
	cr = 8;
	if(cc >= 1) {
	cc = 1;
	}
	}else {
	cr = 7;
	if(cc >= map[cr].length) {
	cr = 8;
	cc = 1;
	}else if(cc == map[cr].length-1){
	cr = 8;
	cc = 0;
	}
	}
	}
	if((cr == 8 && cc == 1) || !visited[cr][cc]) {
	visited[sr][sc] = false;
	visited[cr][cc] = true;
	y[i][0] = cr;
	y[i][1] = cc;
	game(ind + 1, y, s + map[cr][cc], visited);
	visited[cr][cc] = false;
	visited[sr][sc] = true;
	y[i][0] = sr;
	y[i][1] = sc;
	}
	}
	}
	}

view raw BOJ17825.java hosted with ❤ by GitHub