[BOJ] 17825 : 주사위 윷놀이 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. 윷놀이 판을 나타내는 road를 바깥외곽으로 도는 길, 10을 만나서 꺾이는 길, 20을 만나서 꺾이는 길, 30을 만나서 꺾이는 길, 25를 만나서 꺾이는 길, 마지막 40 으로 총 6가지 길로 표현한다.

2. 백트레킹을 이용해 4가지의 말을 움직이는 순서에 대한 모든 경우의 수를 구한다.

3. 말을 움직여 게임을 진행한다.

- 현재 움직일 말이 이미 도착 지점을 지난 경우는 진행되면 안되는 게임이므로 게임을 멈춘다.

- 현재 말의 위치가 10, 20, 30이면(파란색윳놀이판) 다른 road로 바꿔준다.

- 말을 움직이는데 움직였을 때, 해당 road를 벗어난다면 새로운 road로 길을 바꿔주고 아니라면 그냥 진행한다.

( 이때, 한 번에 두 가지 road를 건너뛰는 경우가 있으므로 주의해야한다. 예를 들어 road[0] 윳놀이판 '10' 에서 5칸을 지나가면 road[1] '13', '16', '19' 를 다 지나고 road[4] 로 넘어가야한다. )

- 움직인 말이 다른 말과 윳놀이 판에서 겹친다면 게임을 끝내고, 아니라면 합을 더해준다.

( check배열은 현재 윳놀이 판 해당 지점에 말이 있는지 없는지, checkHorse는 i번 째 말이 도착지점을 지나갔는지를 나타낸다. ) 

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

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

int dice[10], ans = -1, maxLength[6] = { 20, 3, 2, 3, 3, 1 };

void playGame(vector<int> v) {
	bool check[6][30] = {};
	bool checkHorse[4] = {};
	pair<int, int> horse[4] = { {0, 0}, {0, 0}, {0, 0}, {0, 0} };
	int sum = 0;

	for (int i = 0; i < 10; i++) { // v[i]번째 말 선택, dice[i]만큼이동.
		if (checkHorse[v[i]]) // 지금 움직일 말이 이미 도착선을 지남 --> 그런 경우는 Pass
			return;

		check[horse[v[i]].first][horse[v[i]].second] = false; // 이동할것이므로 check 해제.
		// 이동하기전에 길이 바뀌는 경우 셋팅
		if (horse[v[i]].first == 0 && horse[v[i]].second == 5)
			horse[v[i]].first = 1, horse[v[i]].second = -1;
		else if (horse[v[i]].first == 0 && horse[v[i]].second == 10)
			horse[v[i]].first = 2, horse[v[i]].second = -1;
		else if (horse[v[i]].first == 0 && horse[v[i]].second == 15)
			horse[v[i]].first = 3, horse[v[i]].second = -1;

		// 이동하자.
		if (horse[v[i]].second + dice[i] >= maxLength[horse[v[i]].first]) { // 해당 길이 끝나서 다른 길로 가야됨.
			if (horse[v[i]].first == 0 || horse[v[i]].first == 4) {
				horse[v[i]].second = dice[i] - (maxLength[horse[v[i]].first] - horse[v[i]].second);
				horse[v[i]].first = 5;
			}
			else if (horse[v[i]].first == 5)
				checkHorse[v[i]] = true;
			else {
				horse[v[i]].second = dice[i] - (maxLength[horse[v[i]].first] - horse[v[i]].second);
				horse[v[i]].first = 4;
			}
			// 다른 길로 갔는데도 또 넘어가는 경우!
			if (horse[v[i]].second >= maxLength[horse[v[i]].first]) {
				if (horse[v[i]].first == 4) {
					horse[v[i]].second = horse[v[i]].second - maxLength[horse[v[i]].first];
					horse[v[i]].first = 5;
				}
				else if(horse[v[i]].first != 5){
					horse[v[i]].second = horse[v[i]].second - maxLength[horse[v[i]].first];
					horse[v[i]].first = 4;
				}
			}
		}
		else
			horse[v[i]].second += dice[i];

		// 이동했는데 이미 말이 있는 경우.
		if (check[horse[v[i]].first][horse[v[i]].second])
			return;
		// 말이 도착지점 밖으로 나가지 않았더라면 값 sum
		if (!checkHorse[v[i]]) {
			check[horse[v[i]].first][horse[v[i]].second] = true;
			sum += road[horse[v[i]].first][horse[v[i]].second];
		}
	}
	ans = max(ans, sum);
	return;
}

void Backtracking(vector<int> v) {
	if (v.size() == 10) {
		playGame(v);
		return;
	}
	for (int i = 0; i < 4; i++) {
		v.push_back(i);
		Backtracking(v);
		v.pop_back();
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	for (int i = 0; i < 10; i++)
		cin >> dice[i];
	vector<int> v;
	Backtracking(v);

	cout << ans;
}

---