[JAVA] BOJ 백준 17825 주사위 윷놀이

https://www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

풀이 방법

1. 미리 주사위가 도착하는 칸의 점수들을 저장해준다. (이때 하나 이상이 닿을 수 있는 곳이면 따로 배열을 만들어주는 것이 좋다.)
2. 중복 순열을 이용하여 이동할 말을 정하고 이동 구역에 말이 있는 지 조사한 뒤 이동한다.

전체 코드

import java.util.*;
import java.io.*;

public class Main {
	static int[] dice;
	static int[][] hores;
	static int result;
	static int[][] map = new int[5][];
	static int[] dx = {-1, 0, 0, 1};
	static int[] dy = {0, -1, 1, 0};
	public static void main(String[] args) throws Exception {
	   BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	   dice = new int[10];
	   hores = new int[4][2];
	   map[0] = new int[] {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};
	   map[1] = new int[] {0, 13, 16, 19};
	   map[2] = new int[] {0, 22, 24};
	   map[3] = new int[] {0, 28, 27, 26};
	   map[4] = new int[] {0, 25, 30, 35};
	   StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
	   for(int i=0; i<10; i++)
		   dice[i] = Integer.parseInt(st.nextToken());
	   move(0, 0);
	   System.out.println(result);
	}
	static void move(int cnt, int sum) {
		if(cnt == 10) {
			if(result < sum) result = sum;
			return;
		}
		c: for(int i=0; i<4; i++) { // 위치 인덱스, 맵 선택 인덱스
			if(hores[i][0] == 'e') continue;
			int x = hores[i][0]; int m = hores[i][1];
			if(hores[i][1] == 0 && hores[i][0] % 5 == 0 && hores[i][0] < 20) {
				hores[i][1] = hores[i][0] / 5; hores[i][0] = 0;
			}
			hores[i][0] += dice[cnt];
			if(hores[i][1] == 0 && hores[i][0] >= map[0].length)
				hores[i][0] = 'e';
			if(hores[i][1] > 0 && hores[i][1] < 4 && hores[i][0] >= map[hores[i][1]].length) {
				hores[i][0] = hores[i][0] - map[hores[i][1]].length + 1;
				hores[i][1] = 4;
			}
			if(hores[i][1] == 4 && hores[i][0] >= map[hores[i][1]].length) {
				hores[i][0] = hores[i][0] - map[hores[i][1]].length;
				hores[i][1] = 0;
				if(hores[i][0] > 0) hores[i][0] = 'e';
				else hores[i][0] = 20;
			}
			if(hores[i][0] != 'e') {
				for(int k=0; k<4; k++)
					if(k == i) continue;
					else if(hores[k][0] == hores[i][0] && hores[k][1] == hores[i][1]) {
						hores[i][0] = x; hores[i][1] = m;
						continue c;
				}
			}
			if(hores[i][0] == 'e')
				move(cnt+1, sum);
			else
				move(cnt+1, sum+map[hores[i][1]][hores[i][0]]);
			hores[i][0] = x; hores[i][1] = m;
		}
	}
}

한줄씩 살펴보자

static int[] dice;
static int[][] hores;
static int result;
static int[][] map = new int[5][];

dice에는 주사위 정보 10개를 담아줄 것이다.

hores는 말의 정보이다. index 0에는 말의 위치, index 1에는 말이 어떤 map에 있는지를 저장해준다.

map에 미리 보드의 점수를 저장해준다.

dice = new int[10];
 hores = new int[4][2];
 map[0] = new int[] {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};
 map[1] = new int[] {0, 13, 16, 19};
 map[2] = new int[] {0, 22, 24};
 map[3] = new int[] {0, 28, 27, 26};
 map[4] = new int[] {0, 25, 30, 35};
 StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
 for(int i=0; i<10; i++)
   dice[i] = Integer.parseInt(st.nextToken());

나는 다음과 같이 map의 정보를 저장하였다.

static void move(int cnt, int sum) {
		if(cnt == 10) {
			if(result < sum) result = sum;
			return;
		}

move()를 통해 중복 순열을 구현할 것이다. 따라서 visited는 필요없다. 이떄 파라미터 cnt는 몇번째 주사위를 굴린 것인지, sum은 여태까지 점수의 합을 저장하고 있다.

기저조건에 의해 10번을 다 굴렸으면 result에 sum을 갱신해준다. 그리고 return

c: for(int i=0; i<4; i++) { // 위치 인덱스, 맵 선택 인덱스
			if(hores[i][0] == 'e') continue;
			int x = hores[i][0]; int m = hores[i][1];
			if(hores[i][1] == 0 && hores[i][0] % 5 == 0 && hores[i][0] < 20) {
				hores[i][1] = hores[i][0] / 5; hores[i][0] = 0;
			}

for문으로 어떤 말에 이번 주사위를 적용할지 고른다. 이미 말이 끝에 닿았다면 더 이상 이동할수 없으므로 continue

x와 m에 현재 말의 정보들을 저장해놓는다.

첫번째 map에서 10, 20, 30의 index는 각각 5, 10, 15로 5의 배수이다. 이 위치에서 출발하는 경우 map의 정보가 바뀌게 된다. 이때 map은 index를 5로 나눈 몫과 동일하므로 다음과 같이 말의 정보를 바꾼다.(20이하인 이유는 40은 map이 변하지 않기 때문)

hores[i][0] += dice[cnt];
if(hores[i][1] == 0 && hores[i][0] >= map[0].length)
	hores[i][0] = 'e';
if(hores[i][1] > 0 && hores[i][1] < 4 && hores[i][0] >= map[hores[i][1]].length) {
	hores[i][0] = hores[i][0] - map[hores[i][1]].length + 1;
	hores[i][1] = 4;
}
if(hores[i][1] == 4 && hores[i][0] >= map[hores[i][1]].length) {
	hores[i][0] = hores[i][0] - map[hores[i][1]].length;
	hores[i][1] = 0;
	if(hores[i][0] > 0) hores[i][0] = 'e';
	else hores[i][0] = 20;
}

이동할 map을 결정했으므로 이제 이동을 해줄 것이다.

말의 index에 dice를 더해서 이동해주고 첫번째 if문으로 말을 종료 지점에 가는 경우를 찾는다.

두번째 if문에서 map 1, 2, 3인 경우이고 index가 최대 길이를 넘어가는 경우 map 4로 이동해준다. 이때 이동한 길이만큼 줄여주는 것을 잊으면 안된다.

마지막 if문에서 도착하는 경우를 처리해준다.

이때 마지막 if문은 else if로 처리하면 안된다! 두번째에서 변경된 값이 세번째 if를 만족하는 경우가 존재하기 때문이다.

if(hores[i][0] != 'e') {
				for(int k=0; k<4; k++)
					if(k == i) continue;
					else if(hores[k][0] == hores[i][0] && hores[k][1] == hores[i][1]) {
						hores[i][0] = x; hores[i][1] = m;
						continue c;
				}
			}

마지막으로 말의 정보들을 확인하며 현재 위치에 다른 말이 존재하는지 확인해주고 있으면 처음에 저장한 값으로 다시 되돌려준뒤 continue를 해준다.

			if(hores[i][0] == 'e')
				move(cnt+1, sum);
			else
				move(cnt+1, sum+map[hores[i][1]][hores[i][0]]);
			hores[i][0] = x; hores[i][1] = m;
		}
	}
}

말이 마지막 도착점에 닿는다면 점수를 얻지 못하기 때문에 sum에 아무값도 더하지 않는다.

그게 아니라면 현재 머물고 있는 주사위 점수를 더하여 재귀를 호출한다.