[BOJ] 17825 주사위 윷놀이

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

17825번: 주사위 윷놀이

작년 삼성 하반기 기출문제

2달 전쯤에 풀었는데, 그 때 예외케이스를 찾지 못해서 못 푼 상태로 끝났었다.

그 상태로 방치해뒀다가 이번에 아예 새로 풀었는데 한번에 통과했다.

그 전에 고민 많이 했던 문제라 문제에 대한 분석이 확실 했던 듯 하다.

원래 알던 문제라 문제를 읽는 과정, 주의해야 할 부분에서 얻어갈 것은 별로 없었고 그냥 구현력만 좀 향상시킬 수 있었다..

 

 

문제

말이 4개 있고, 1~5까지 있는 주사위를 던져서 나올 수 10개를 미리 알고 있을 떄, 얻을 수 있는 최댓값 구하기

 

 

풀이

그냥 중복순열 그리고 시뮬레이션 그 자체.

말판 및 여러가지 필요한 정보들을 어떤 자료구조에 저장할지를 조금 고민 했었고

파란 화살표를 타고 가는 경우 등 예외의 경우를 처리할게 좀 있었다.

 

1. 먼저, 4개의 말(0~3)을 중복 순열로 10개 뽑는다. 이때 i번째 말은 i번째 주사위 숫자 만큼 이동할 것이다.
2. 각각의 경우에 대해서 턴 마다, 말들을 이동시킨다. 이 때 조심할 것은 다음에 이동할 칸에 이미 말이 있으면 그 경우는 배제해야한다.
3. 얻을 수 있는 점수의 최댓값을 구한다.

 

 

실수 했던 부분

• 다음에 이동할 칸에 말이 있을 경우 return해 주어야 하는데, continue 해주어서 엄청나게 틀렸었다.
• 말판 가운데에 있는 25, 30, 35, 40과 같은 경우 내가 설정한 말판 구조에 의하면, 이미 말판이 올려져 있는 칸 위에 말판을 올리는 경우가 있었는데, 주의 해야 한다.
• exist[i][j] = true 하는 과정을 빼먹었다. 
• 또한 초기화 관련하여 실수할 뻔..

실수 줄여서 한번에 통과하자..................

 

 

 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int answer;
int dice[10];
int turn[10];
vector<vector<int>> board =
{ {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40},
{10, 13, 16, 19, 25, 30, 35, 40},
{20, 22, 24, 25, 30, 35, 40},
{30, 28, 27, 26, 25, 30, 35, 40}};
bool exist[4][21];
pair<int,int> position[4];

void game() {
	int sum = 0;
	for (int i = 0; i < 10; i++) {
		int cur = turn[i];
		int boardNum = position[cur].first;
		int pos = position[cur].second;
		int nextPos = pos + dice[i];
		
		//이미 도착한 경우
		if (position[cur].first == -1) continue;

		//도착한 경우
		if (nextPos >= board[boardNum].size()) {
			exist[boardNum][pos] = false;
			position[cur] = { -1,-1 };
			continue;
		}

		//다음에 가야할 지점이 10인 경우
		if (boardNum == 0 && board[boardNum][nextPos] == 10) {
			if (exist[1][0]) return;
			exist[0][pos] = false;
			sum += 10;
			position[cur] = { 1, 0 };
			exist[1][0] = true;
			continue;
		}
		
		//다음에 가야할 지점이 20인 경우
		if (boardNum == 0 && board[boardNum][nextPos] == 20) {
			if (exist[2][0]) return;
			exist[0][pos] = false;
			sum += 20;
			position[cur] = { 2, 0 };
			exist[2][0] = true;
			continue;
		}
		
		//다음에 가야할 지점이 30인 경우
		if (boardNum == 0 && board[boardNum][nextPos] == 30) {
			if (exist[3][0]) return;
			exist[0][pos] = false;
			sum += 30;
			position[cur] = { 3, 0 };
			exist[3][0] = true;
			continue;
		}

		//다음에 가야할 지점이 25, 30, 35인 경우
		if (board[boardNum][nextPos] == 25 || board[boardNum][nextPos] == 30 ||
			board[boardNum][nextPos] == 35) {
			if (board[boardNum][nextPos] == 25 && (exist[1][4] || exist[2][3] || exist[3][4])) return;
			if (board[boardNum][nextPos] == 30 && (exist[1][5] || exist[2][4] || exist[3][5])) return;
			if (board[boardNum][nextPos] == 35 && (exist[1][6] || exist[2][5] || exist[3][6])) return;
			exist[boardNum][pos] = false;
			sum += board[boardNum][nextPos];
			position[cur] = { boardNum, nextPos };
			exist[boardNum][nextPos] = true;
			continue;
		}

		//다음에 가야할 지점이 40인 경우
		if (board[boardNum][nextPos] == 40) {
			if (exist[0][20] || exist[1][7] || exist[2][6] || exist[3][7]) return;
			exist[boardNum][pos] = false;
			sum += 40;
			position[cur] = { boardNum, nextPos };
			exist[boardNum][nextPos] = true;
			continue;
		}

		//그 외의 경우
		if (exist[boardNum][nextPos]) return;
		exist[boardNum][pos] = false;
		sum += board[boardNum][nextPos];
		position[cur] = { boardNum, nextPos };
		exist[boardNum][nextPos] = true;
	}

	answer = max(answer, sum);
}
void init() {
	for (int i = 0; i < 4; i++) {
		position[i] = { 0, 0 };
		for (int j = 0; j < 21; j++) {
			exist[i][j] = false;
		}
	}
}
void dfs(int depth) {
	if (depth == 10) {
		init();
		game();
		return;
	}
	for (int i = 0; i < 4; i++) {
		turn[depth] = i;
		dfs(depth + 1);
	}
}

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