[PS][기출문제][삼성]/[BOJ][17825][주사위 윷놀이]

boj17825.cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class HORSE {
public:
	int pos;
	HORSE() {
		pos = 0;
	}
};

int dice[10]; //입력받은 주사위 결과
int order[10];//어떤 말을 움직일지 brute-force
vector<int> overlap[33];//말들이 겹치는지 판단ㄴ
vector<int> map[33];//연결된 노드들 저장
HORSE horse[4]; //현재 말의 위치
int ans = 0;
bool flag = false;
int score[33] = { //각 노드별 idx부여
	0,2,4,6,8,
	10,12,14,16,18,
	20,22,24,26,28,
	30,32,34,36,38,
	22,24,25,30,35,
	13,16,19,28,27,
	26,40,0
};

int dfs(int origin, int curr, int step) {
	if (curr == 32) return 32;
	if (step == 0) {
		return curr;
	}
	if (origin == curr) {
		if (curr == 5) return dfs(origin, 25, step - 1);
		else if (curr == 10) return dfs(origin, 20, step - 1);
		else if (curr == 15) return dfs(origin, 28, step - 1);
	}
	return dfs(origin, map[curr][0], step - 1);
}

int cast_dice(int x) {
	int h = order[x];
	int step = dice[x];
	int curr = horse[h].pos;
	if (curr == -1) return 0;
	int next = dfs(curr, curr, step);
	if (next == 32) {
		if (!overlap[curr].empty()) overlap[curr].pop_back();
		horse[h].pos = -1;
		return 0;
	}
	if (overlap[next].size() == 0) {
		if (!overlap[curr].empty()) overlap[curr].pop_back();
		overlap[next].push_back(x);
		horse[h].pos = next;
		return score[next];
	}
	else {
		return -1;
	}
}


void solve(void) {
	int tans = 0, ret = 0;
	for (int i = 0; i < 10; i++) {
		ret = cast_dice(i);
		if (ret > 0) {
			tans += ret;
		}
		else if (ret == -1) {
			break;
		}
	}
	if (ret != -1) ans = ans < tans ? tans : ans;

}

void brute(int depth) {
	if (depth == 10) {
		for (int i = 0; i < 4; i++) {
			horse[i].pos = 0;
		}
		for (int i = 0; i < 33; i++) {
			overlap[i].clear();
		}
		solve();
		return;
	}
	for (int i = 0; i < 4; i++) {
		order[depth] = i;
		brute(depth + 1);
	}
}

void readMap(void) {
	//원
	for (int i = 0; i <= 18; i++) {
		map[i].push_back(i + 1);
	}
	map[19].push_back(31);
	//가운데 위로
	map[10].push_back(20);
	for (int i = 20; i <= 23; i++) {
		map[i].push_back(i + 1);
	}
	map[24].push_back(31);
	//왼쪽에서 오른쪽
	map[5].push_back(25);
	for (int i = 25; i <= 26; i++) {
		map[i].push_back(i + 1);
	}
	map[27].push_back(22);
	//오른쪽에서 왼쪽
	map[15].push_back(28);
	for (int i = 28; i <= 29; i++) {
		map[i].push_back(i + 1);
	}
	map[30].push_back(22);
	map[31].push_back(32);
}

int main(void) {
	readMap();
	for (int i = 0; i < 10; i++) {
		cin >> dice[i];
	}
	brute(0);
	cout << ans << "\n";
	return 0;
}