[백준] 17825번 주사위 윷놀이

17825번: 주사위 윷놀이

주사위를 던질 때마다 선택할 수 있는 말은 4가지이고

주사위는 10번 던지므로

말을 이동하는 총 경우의 수는 4^10가지가 된다. (중복 순열)

 

게임판에서 말이 어떤 파란색 칸으로 이동하는지에 따라

경로가 달라진다.

 

1. 파란색 칸을 한 번도 밟지 않는 경우 (Default)

 

 

 

 

2. 1번 경로로 가다가 첫 번째 파란색 칸을 밟는 경우

 

 

 

3. 1번 경로로 가다가 두 번째 파란색 칸을 밟는 경우

 

 

 

4. 1번 경로로 가다가 세 번째 파란색 칸을 밟는 경우

 

 

 

이 네 가지 경우에 따른 경로를

이차원 배열 board에 저장해준다.

 

말을 이동시킬 때

같은 칸에 두 개 이상의 말이 있으면 안 되므로

A 말을 이동시키려는 칸에 다른 말 B가 있는지 검사해줘야 한다.

 

여기서 주의할 점은

A와 B 둘 다 같은 경로일 땐 같은 숫자를 밟고 있으면 겹치는 칸으로 간주하면 되는데

 

A와 B 둘 다 다른 경로일 땐 같은 숫자를 밟고 있어도 겹치는 칸이 아닌 경우가 있다.

ex) A의 경로 : 3번 경로, 이동시키려는 칸 : 22

B의 경로 : 1번 경로, 밟고 있는 칸 : 22

이런 경우 칸 22는 서로 다른 칸이다.

 

A의 경로 : 3번 경로, 이동시키려는 칸 : 30

B의 경로 : 4번 경로, 밟고 있는 칸 : 30

이런 경우도 칸 30은 서로 다른 칸이다.

 

또, A와 B 둘 다 다른 경로면서 같은 숫자를 밟고 있고 그게 겹치는 칸인 경우도 있다.

ex) A의 경로 : 2번 경로, 이동시키려는 칸 : 25

B의 경로 : 4번 경로, 밟고 있는 칸 : 25

이런 경우 칸 25는 겹치는 칸이다.

 

이 경우를 매우 유의해서 걸러 주어야 한다.

나는

5의 배수(30 제외)를 밟고 있을 때와

30을 밟고 있고 30 직전 칸(28 혹은 25)이 A와 B 둘 다 같을 때를

겹치는 칸으로 걸러주었다.

 

1번 경로로 말을 이동하면서 파란 칸을 밟게 되면

그 칸에 맞게 경로를 변경시켜주고

재귀 호출에서 빠져나올 땐

변경된 경로를 다시 1번 경로로 바꿔준다.

 

10회 반복할 때마다 그때의 점수의 합을 구해서 최댓값을 갱신한다.

#include <iostream>
#include <algorithm>
using namespace std;
int dice[10], marker[4], num[4], score[4], board[4][30], res, tmp;
bool finish[4] = { false };
void Permutation(int cnt) {
	if (cnt == 10) {
		for (int i = 0; i < 4; i++) tmp += score[i];
		res = max(res, tmp), tmp = 0;
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (finish[i]) continue;
		bool nope = false;
		for (int j = 0; j < 4; j++) { // 이동하려는 칸에 다른 말이 있는지 확인해준다
			if (i == j || marker[j] == 0 || finish[j]) continue;
			if (board[num[i]][marker[i] + dice[cnt]] == board[num[j]][marker[j]]) {
				if (num[i] == num[j]) nope = true;
				else if (num[i] != num[j]) {
					if (board[num[j]][marker[j]] % 5 == 0 && board[num[j]][marker[j]] != 30) nope = true;
					else if (board[num[j]][marker[j]] == 30 && board[num[j]][marker[j] - 1] == board[num[i]][marker[i] + dice[cnt] - 1]) nope = true;
				}
				if (nope) break;
			}
		}
		if (nope) continue;

		marker[i] += dice[cnt]; // 주사위 이동

		if (num[i] == 0 && board[num[i]][marker[i]] == 10) num[i] = 1; // 전환점에 있는지 확인
		else if (num[i] == 0 && board[num[i]][marker[i]] == 20) num[i] = 2;
		else if (num[i] == 0 && board[num[i]][marker[i]] == 30) num[i] = 3;

		if (board[num[i]][marker[i]] == 0) finish[i] = true; // 도착한 말은 표시해줌
		else score[i] += board[num[i]][marker[i]]; // 점수 갱신

		Permutation(cnt + 1); // 다음 주사위

		if (!finish[i]) score[i] -= board[num[i]][marker[i]];
		else finish[i] = false;

		if (num[i] == 1 && board[num[i]][marker[i]] == 10) num[i] = 0; // 전환점에 있는지 확인
		else if (num[i] == 2 && board[num[i]][marker[i]] == 20) num[i] = 0;
		else if (num[i] == 3 && marker[i] == 15) num[i] = 0;

		marker[i] -= dice[cnt];
	}
}
int main() {
	for (int i = 0; i < 4; i++) { // 보드판 입력
		int idx = 0;
		for (int j = 1; j <= 20; j++) {
			board[i][j] = j * 2;
			if (j * 2 == i * 10) {
				idx = j + 1;
				break;
			}
		}
		if (i == 0) continue;
		if (i == 1) board[i][idx++] = 13, board[i][idx++] = 16, board[i][idx++] = 19;
		else if (i == 2) board[i][idx++] = 22, board[i][idx++] = 24;
		else if (i == 3) board[i][idx++] = 28, board[i][idx++] = 27, board[i][idx++] = 26;
		for (int j = idx; j < idx + 4; j++) board[i][j] = 25 + 5 * (j - idx);
	}
	for (int i = 0; i < 10; i++) cin >> dice[i];
	Permutation(0);
	cout << res;
	return 0;
}