17825 주사위 윷놀이

경로를 총 5개로 나눠서 풀었음

백트래킹하면 더 빨리 풀듯

#include <iostream>
#include <queue>

using namespace std;

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

int dis_map[5] = {20, 4, 3, 4, 4};
int dice[10] = {};
int result = 0;

typedef struct m {
	bool finished[4] = {};
	int finish_cnt = 0;
	int usingmap[4] = {};
	int point[4] = {};
	int turn = 0;
	int cnt = 0;
}MARKERS;

void input() {
	for (int i = 0; i < 10; i++)
		cin >> dice[i];
}

void show(MARKERS marker) {
	for (int i = 0; i < 4; i++) {
		cout << "marker" << i << ":" << marker.usingmap[i] << ' ' << marker.point[i] << endl;
	}
	cout << "cnt : " << marker.cnt << endl;
}

void solve() {
	queue<MARKERS> q;

	MARKERS markers;
	q.push(markers);

	while (!q.empty()) {
		MARKERS now = q.front();
		//show(now);
		if (now.turn == 10 || now.finish_cnt == 4) {
			//if (result < now.cnt) show(now);
			result = (result < now.cnt) ? now.cnt : result;		
			q.pop();
			continue;
		}

		for (int i = 0; i < 4; i++) {
			MARKERS move = q.front();
			if (move.finished[i]) continue;

			// move
			move.point[i] += dice[move.turn];
			move.turn++;
			
			bool end_flag = false;
			if (move.point[i] >= dis_map[move.usingmap[i]]) {
				if (move.usingmap[i] == 0) {
					if (move.point[i] == dis_map[0]) {
						move.usingmap[i] = 4;
						move.point[i] = 3;
					}
					else {
						move.finished[i] = true;
						end_flag = true;
					}
				}
				else if (move.usingmap[i] < 4) {
					move.point[i] -= dis_map[move.usingmap[i]];
					move.usingmap[i] = 4;
				}

				if (move.usingmap[i] == 4 && 
					move.point[i] >= dis_map[move.usingmap[i]]) {
					move.finished[i] = true;
					end_flag = true;
				}
			}
			else {
				if (move.usingmap[i] == 0 &&
					score_map[0][move.point[i]] % 10 == 0) {
					move.usingmap[i] = score_map[0][move.point[i]] / 10;
					move.point[i] = 0;
				}
			}

			// check
			if (!end_flag) {
				bool check_flag = false;
				for (int j = 0; j < 4; j++) {
					if (move.finished[i] || i == j) continue;

					if (move.point[i] == move.point[j]
						&& move.usingmap[i] == move.usingmap[j]) {
						check_flag = true;
						break;
					}
				}

				if (check_flag) continue;

				move.cnt += score_map[move.usingmap[i]][move.point[i]];
			}

			q.push(move);
		}

		q.pop();
		
	}

}

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

	input();
	solve();
	cout << result;
}