백준 / 17825 주사위 윷놀이 C++

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

처음에는 하드코딩으로 길을 열심히 만들어 하려했는데 너무 햇갈려서 때려치웠다.

두 번째로 경로 별로 indexing 하여 파란칸인지 아닌지를 결정하려 했지만, 중간에 도착지점이 끼어있다고 생각하니 말이 도착 지점 이동 후에 엉뚱한 곳으로 가는 경우가 발생하여 접었다.

그래서 다른 분들의 풀이를 참고하였다.

 

map의 칸의 index와 점수를 구분하여 게임을 한다. (이렇게 안 하고 map 배열 하나로 처리하려 해서 너무 햇갈렸다.)

파란 칸인 경우는 turn 배열을 이용해 해당 index의 turn값이 0이 아니면 파란 경로란 의미이다. 

 

indexing은 다음과 같다. map 배열을 다음에 나올 index라 생각하면 된다.

먼저 시작 점은 0, 도착 점은 21이다. 그리고 1~20까지 바깥 경로를 따라 간다.

그리고 10에서 출발하는 파란 경로에서 22~27을 대응한다. 그리고 map[27]=20이다. (20번째는 숫자 40인 칸)

그리고 30에서 출발하는 파란 경로를 28~30 으로 대응한다. map[30]=25이다. (가운데 큰 25로 위치하므로)

그리고 20에서 출발하는 파란 경로를 31, 32 로 대응한다. map[32]=25이다. (가운데 큰 25로 위치하므로)

 

이렇게 map을 구성한 뒤 dfs를 이용해 해당 말을 이동시키면 된다.

 

코드는 다음과 같다.

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

// 주사위
int dice[10];
// 전체 맵 map[21]=end
int map[40];
// 해당 칸에 말 여부
bool check[40];
// 파란 칸에서 회전하는 경우 체크
int turn[40];
// 말의 위치
int horse[4];
// 점수
int score[40];
// 최종 점수
int result = 0;

void init()
{
	for (int i = 0; i < 10; i++)
		cin >> dice[i];
	memset(check, false, sizeof(check));
	
	for (int i = 0; i < 21; i++)
		map[i] = i + 1;
	map[21] = 21; // 도착 지점
	for (int i = 22; i < 27; i++)
		map[i] = i + 1;
	map[28] = 29;
	map[29] = 30;
	map[30] = 25;
	map[31] = 32;
	map[32] = 25;
	map[27] = 20;

	turn[5] = 22;
	turn[10] = 31;
	turn[15] = 28;
	turn[25] = 26;

	for (int i = 0; i < 21; i++)
		score[i] = i * 2;
	score[22] = 13;
	score[23] = 16;
	score[24] = 19;
	score[31] = 22;
	score[32] = 24;
	score[28] = 28;
	score[29] = 27;
	score[30] = 26;
	score[25] = 25;
	score[26] = 30;
	score[27] = 35;
}

void dfs(int cnt, int sum)
{
	if (cnt == 10) {
		result = max(result, sum);
		return;
	}

	for (int i = 0; i < 4; i++) {

		// 말의 현재 위치, 이동할 위치
		// 우선 현재 위치와 동일시하게 하여 파란칸인지 체크후 이동
		int now = horse[i];
		int next = horse[i];

		// 이동 횟수
		int move_count = dice[cnt];

		// 파란 칸인 경우
		if (turn[now] != 0) {
			next = turn[now];
			move_count--;
		}

		// 이동
		while (move_count--) {
			next = map[next];
		}

		// 아직 도착 안 했지만 다른 말이 있는 경우
		if (next != 21 && check[next])
			continue;

		check[now] = false;
		check[next] = true;
		horse[i] = next;

		dfs(cnt + 1, sum + score[next]);

		check[now] = true;
		check[next] = false;
		horse[i] = now;
	}
}

int main()
{
	init();
	dfs(0, 0);
	cout << result;
}