알고리즘/Baekjoon
[C++] 백준 17825번 주사위 윷놀이
kimyunseok
2022. 10. 4. 23:16
17825번: 주사위 윷놀이
주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면
www.acmicpc.net
삼성 SW 역량 테스트 기출 문제 수록 문제.
구현 / 시뮬레이션 문제.
어떻게 풀어야 깔끔하게 풀 수 있을 지 모르겠어서 하드 코딩하는 방식으로 해결했다.
WA를 많이 받게 됐는데 하드 코딩으로 구현해서 여러 번 고쳐서 맞출 수 있었다.
문제 조건
문제의 조건들은 다음과 같다.
- 시작 칸의 말이 4개 존재한다.
- 말이 파란색 칸(10, 20, 30)에서 이동할 경우 파란색 화살표를 따라 이동해야 하고,
이외에는 빨간색 화살표로 이동해야 한다.
말이 도착하면 이동 끝. - 게임은 10개의 턴이고, 각 턴마다 1 ~ 5의 주사위가 존재하게 된다.
4개의 말 중 하나를 선택해서 1 ~ 5의 주사위의 칸만큼 이동하게 된다. - 도착할 칸에 다른 말이 있으면 이동해서는 안된다.
- 말의 이동이 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.
조건은 많지 않지만, 고려해야 할 사항이 많다.
문제 구현
처음에 깔끔하게 구현하고 싶었지만 방법이 떠오르지 않았다.
브루트 포스 방법으로 다음과 같이 칸을 나눈 후 구현했다.
(참고로 41은 도착 칸을 의미.)
- 현재 칸이 41일 때 : 넘어간다.
- 현재 칸이 10, 13, 16, 19,20, 22, 24, 25, 26, 27, 28, 30, 30(25 위), 35일 때에는 안쪽 화살표들에 맞춰 이동한다.
- 현재 칸이 40이면 41로 이동시킨다.
- 현재 칸이 그 외의 경우에는 주사위 수*2를 해서 이동시켜준다.
두 번 등장하는 수들도 있으므로, 현재 칸이 안쪽 칸인 지 구분해야 한다.
또한 40을 넘어가지는 않는 지 Check해야 한다.
문제 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Horse {
bool beforeIsBlue = false;
int curNum = 0;
};
vector<Horse> horseVec(4);
vector<int> diceNumVec;
int diceNumFrom10[8] = {
-1, 13, 16, 19, 25, 30, 35, 40
};
int diceNumFrom20[7] = {
-1, 22, 24, 25, 30, 35, 40
};
int diceNumFrom30[8] = {
-1, 28, 27, 26, 25, 30, 35, 40
};
bool isVisit[41][2]; // 두번째 0 : 그냥 , 두번째 1 : 전에 파란칸
int result;
void checkMaxScore(int startIdx, int cnt, int curScore) {
//cout << cnt << " , " << curScore << "\n";
//for (int i = 0; i < 4; i++) {
// cout << horseVec[i].curNum << " ";
//}
//cout << "\n\n";
if (cnt >= 10) {
//cout << curScore << "\n";
//for (int i = 0; i < 4; i++) {
// cout << horseVec[i].curNum << " ";
//}
//cout << "\n\n";
result = max(result, curScore);
}
else {
for (int i = startIdx; i < 10; i++) {
int curDiceNum = diceNumVec[i];
for (int j = 0; j < 4; j++) {
if (horseVec[j].curNum == 41) continue;
if (horseVec[j].curNum == 10) {
if (!isVisit[diceNumFrom10[curDiceNum]][1]) {
int saveNum = horseVec[j].curNum;
isVisit[saveNum][0] = false;
isVisit[diceNumFrom10[curDiceNum]][1] = true;
horseVec[j].beforeIsBlue = true;
horseVec[j].curNum = diceNumFrom10[curDiceNum];
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom10[curDiceNum]);
isVisit[saveNum][0] = true;
isVisit[diceNumFrom10[curDiceNum]][1] = false;
horseVec[j].beforeIsBlue = false;
horseVec[j].curNum = saveNum;
}
}
else if (horseVec[j].curNum == 13 && horseVec[j].beforeIsBlue) {
if (!isVisit[diceNumFrom10[curDiceNum + 1]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom10[curDiceNum + 1];
isVisit[saveNum][1] = false;
isVisit[diceNumFrom10[curDiceNum + 1]][1] = true;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom10[curDiceNum + 1]);
isVisit[diceNumFrom10[curDiceNum + 1]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else if (horseVec[j].curNum == 16 && horseVec[j].beforeIsBlue) {
if (!isVisit[diceNumFrom10[curDiceNum + 2]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom10[curDiceNum + 2];
isVisit[diceNumFrom10[curDiceNum + 2]][1] = true;
isVisit[saveNum][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom10[curDiceNum + 2]);
isVisit[diceNumFrom10[curDiceNum + 2]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else if (horseVec[j].curNum == 19 && horseVec[j].beforeIsBlue) {
if (curDiceNum < 5) {
if (!isVisit[diceNumFrom10[curDiceNum + 3]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom10[curDiceNum + 3];
isVisit[diceNumFrom10[curDiceNum + 3]][1] = true;
isVisit[saveNum][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom10[curDiceNum + 3]);
isVisit[diceNumFrom10[curDiceNum + 3]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else {
horseVec[j].curNum = 41;
isVisit[19][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore);
isVisit[19][1] = true;
horseVec[j].curNum = 19;
}
}
else if (horseVec[j].curNum == 20) {
if (!isVisit[diceNumFrom20[curDiceNum]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom20[curDiceNum];
isVisit[diceNumFrom20[curDiceNum]][1] = true;
isVisit[saveNum][0] = false;
horseVec[j].beforeIsBlue = true;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom20[curDiceNum]);
isVisit[diceNumFrom20[curDiceNum]][1] = false;
isVisit[saveNum][0] = true;
horseVec[j].beforeIsBlue = false;
horseVec[j].curNum = saveNum;
}
}
else if (horseVec[j].curNum == 22 && horseVec[j].beforeIsBlue) {
if (!isVisit[diceNumFrom20[curDiceNum + 1]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom20[curDiceNum + 1];
isVisit[saveNum][1] = false;
isVisit[diceNumFrom20[curDiceNum + 1]][1] = true;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom20[curDiceNum + 1]);
isVisit[diceNumFrom20[curDiceNum + 1]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else if (horseVec[j].curNum == 24 && horseVec[j].beforeIsBlue) {
if (curDiceNum < 5) {
if (!isVisit[diceNumFrom20[curDiceNum + 2]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom20[curDiceNum + 2];
isVisit[diceNumFrom20[curDiceNum + 2]][1] = true;
isVisit[saveNum][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom20[curDiceNum + 2]);
isVisit[diceNumFrom20[curDiceNum + 2]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else {
horseVec[j].curNum = 41;
isVisit[24][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore);
isVisit[24][1] = true;
horseVec[j].curNum = 24;
}
}
else if (horseVec[j].curNum == 28 && horseVec[j].beforeIsBlue) {
if (!isVisit[diceNumFrom30[curDiceNum + 1]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom30[curDiceNum + 1];
isVisit[diceNumFrom30[curDiceNum + 1]][1] = true;
isVisit[saveNum][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom30[curDiceNum + 1]);
isVisit[diceNumFrom30[curDiceNum + 1]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else if (horseVec[j].curNum == 27 && horseVec[j].beforeIsBlue) {
if (!isVisit[diceNumFrom30[curDiceNum + 2]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom30[curDiceNum + 2];
isVisit[diceNumFrom30[curDiceNum + 2]][1] = true;
isVisit[saveNum][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom30[curDiceNum + 2]);
isVisit[diceNumFrom30[curDiceNum + 2]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else if (horseVec[j].curNum == 26 && horseVec[j].beforeIsBlue) {
if (curDiceNum < 5) {
if (!isVisit[diceNumFrom30[curDiceNum + 3]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom30[curDiceNum + 3];
isVisit[diceNumFrom30[curDiceNum + 3]][1] = true;
isVisit[saveNum][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom30[curDiceNum + 3]);
isVisit[diceNumFrom30[curDiceNum + 3]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else {
horseVec[j].curNum = 41;
isVisit[26][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore);
isVisit[26][1] = true;
horseVec[j].curNum = 26;
}
}
else if (horseVec[j].curNum == 30 && !horseVec[j].beforeIsBlue) {
if (!isVisit[diceNumFrom30[curDiceNum]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom30[curDiceNum];
horseVec[j].beforeIsBlue = true;
isVisit[diceNumFrom30[curDiceNum]][1] = true;
isVisit[saveNum][0] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom30[curDiceNum]);
horseVec[j].beforeIsBlue = false;
isVisit[diceNumFrom30[curDiceNum]][1] = false;
isVisit[saveNum][0] = true;
horseVec[j].curNum = saveNum;
}
}
else if (horseVec[j].curNum == 40) {
horseVec[j].curNum = 41;
isVisit[40][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore);
isVisit[40][1] = true;
horseVec[j].curNum = 40;
}
else if (horseVec[j].curNum == 25) {
if (curDiceNum < 4) {
if (!isVisit[diceNumFrom30[curDiceNum + 4]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom30[curDiceNum + 4];
isVisit[diceNumFrom30[curDiceNum + 4]][1] = true;
isVisit[saveNum][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom30[curDiceNum + 4]);
isVisit[diceNumFrom30[curDiceNum + 4]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else {
horseVec[j].curNum = 41;
isVisit[25][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore);
isVisit[25][1] = true;
horseVec[j].curNum = 25;
}
}
else if (horseVec[j].curNum == 30 && horseVec[j].beforeIsBlue) {
if (curDiceNum < 3) {
if (!isVisit[diceNumFrom30[curDiceNum + 5]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom30[curDiceNum + 5];
isVisit[diceNumFrom30[curDiceNum + 5]][1] = true;
isVisit[saveNum][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom30[curDiceNum + 5]);
isVisit[diceNumFrom30[curDiceNum + 5]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else {
horseVec[j].curNum = 41;
isVisit[30][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore);
isVisit[30][1] = true;
horseVec[j].curNum = 30;
}
}
else if (horseVec[j].curNum == 35) {
if (curDiceNum < 2) {
if (!isVisit[diceNumFrom30[curDiceNum + 6]][1]) {
int saveNum = horseVec[j].curNum;
horseVec[j].curNum = diceNumFrom30[curDiceNum + 6];
isVisit[diceNumFrom30[curDiceNum + 6]][1] = true;
isVisit[saveNum][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore + diceNumFrom30[curDiceNum + 6]);
isVisit[diceNumFrom30[curDiceNum + 6]][1] = false;
isVisit[saveNum][1] = true;
horseVec[j].curNum = saveNum;
}
}
else {
horseVec[j].curNum = 41;
isVisit[35][1] = false;
checkMaxScore(i + 1, cnt + 1, curScore);
isVisit[35][1] = true;
horseVec[j].curNum = 35;
}
}
else {
if (horseVec[j].curNum + (curDiceNum * 2) == 40) {
if (!isVisit[horseVec[j].curNum + (curDiceNum * 2)][1]) {
isVisit[horseVec[j].curNum][0] = false;
horseVec[j].curNum += (curDiceNum * 2);
isVisit[horseVec[j].curNum][1] = true;
checkMaxScore(i + 1, cnt + 1, curScore + horseVec[j].curNum);
isVisit[horseVec[j].curNum][1] = false;
horseVec[j].curNum -= (curDiceNum * 2);
isVisit[horseVec[j].curNum][0] = true;
}
}
else if (horseVec[j].curNum + (curDiceNum * 2) > 40) {
int saveNum = horseVec[j].curNum;
isVisit[horseVec[j].curNum][0] = false;
horseVec[j].curNum = 41;
checkMaxScore(i + 1, cnt + 1, curScore);
horseVec[j].curNum = saveNum;
isVisit[horseVec[j].curNum][0] = true;
}
else {
if (!isVisit[horseVec[j].curNum + (curDiceNum * 2)][0]) {
isVisit[horseVec[j].curNum][0] = false;
horseVec[j].curNum += (curDiceNum * 2);
isVisit[horseVec[j].curNum][0] = true;
checkMaxScore(i + 1, cnt + 1, curScore + horseVec[j].curNum);
isVisit[horseVec[j].curNum][0] = false;
horseVec[j].curNum -= (curDiceNum * 2);
isVisit[horseVec[j].curNum][0] = true;
}
}
}
}
}
}
}
int main() {
int input;
for (int i = 1; i <= 10; i++) {
cin >> input;
diceNumVec.push_back(input);
}
checkMaxScore(0, 0, 0);
cout << result;
return 0;
}
하드코딩하면서 구현하다보니 놓친 조건들이 많이 있었다.