[백준 17825: 주사위 윷놀이] (C++)

삼성 SW 역량 테스트

https://www.acmicpc.net/workbook/view/1152

ㄴ주사위 윷놀이

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

 

 

 

l 문제

 

1. 주사위를 굴려서 나온 수 만큼 말을 이동시키는 윷놀이 게임이다. 일반적인 윷놀이 게임과 규칙은 동일하지만 첫 번째 코너를 밟고나서 중앙을 밟지 않아도 무조건 도착 지점으로 꺾는다. ( 원래 윷놀이는 중앙을 밟지 않으면 그대로 직진 )

2. 말 처음 시작 지점에 말 4개가 있다.  말은 순서와 상관 없이 아무 말이나 이동시킬 수 있고 이동하려는 칸에 이미 말이 있으면 이동할 수 없다. ( 시작, 도착 칸 제외 ) 도착 지점 넘어가면 도착 지점에서 이동을 마치며, 도착한 말은 더 이상 이동할 수 없다. 말이 이동을 마칠때마다 칸에 적혀있는 수가 점수에 추가된다.

3. 주사위 5면 주사위의 각 면에 1 ~ 5 까지의 수가 적혀있다 주사위를 굴려서 나온 수 만큼 말을 이동시킬 수 있다. 주사위에서 나올 수 10개가 순서대로 입력으로 주어짐

 

 

l 입력

 

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

 

 

l 출력

 

얻을 수 있는 점수의 최댓값을 출력한다.

 

 

l 주의

 

이 문제는 평범한 윷놀이가 아닙니다.

원래 윷놀이는 코너( 10 )을 밟으면 지름길로 가서 중앙( 25 )를 밟아야 도착 지점으로 꺾을 수 있는데

이 문제는 중앙을 밟지 않아도 무조건 도착 지점으로 꺾어야 합니다.

 

이 윷놀이는 도착 지점까지 4가지 경로가 있습니다.

일반적인 경로

가로 통로를 따라 오른쪽 방향으로

세로 통로를 따라 위로

가로 통로를 따라 왼쪽 방향으로

l 풀이

 

DFS로 이동시킬 말을 선택하고 시뮬레이션

말 이동 함수 {   1. 코너에 진입한 경우   2. 가로 통로 - 오른쪽 방향   3. 가로 통로 - 왼쪽 방향   4. 도착지점 넘어간 경우   그외에 일반적인 경우 } DFS 함수 {   1. 말 4개를 차례대로 진행   2. 말 이동 함수   3. 이동한 위치에 다른 말이 존재하면 넘어감   4. DFS 함수( 다음 턴 ) }

윷놀이 판

일반적인 경로, 코너 3개, 가로 통로, 세로 통로, 중앙 이렇게 분리하여 생각하였습니다. 코너를 밟게 되면 통로로 들어가게 되고 세로 통로는 그대로 직진하고 가로 통로는 ( 말 위치 + 주사위 수 )가 통로 길이를 넘어가면 도착 지점 쪽으로 꺾어서 진행하도록 하였습니다. 윷놀이 판

통로 번호

통로 번호를 어떻게 지정할지 참 애먹었는데 일반 경로 1 ~ 20, 도착이 21 가로 통로( R ) 26, 27, 28 가로 통로( L ) 45, 46, 47 세로 통로 34, 35, 36, 37, 38, 39 ( 39은 20으로 취급 ) 이렇게 지정한 이유는 주사위 수가 최대 5이기 때문에 20 + 5 = 25 보다 큰 26부터 ~ 28 28 + 5 = 33 보다 큰 34 부터 ~ 39 39 + 5 = 44 보다 큰 45 부터 ~ 47 뭐 이런 식으로 통로 번호를 지정해주었습니다. 사실 경로 4개 다 따로 범위 정해주고 각각 배열에 다 때려넣어서 해도 될 것 같습니다.

 

 

l  코드

 

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int TURNEL_GOAL = 44, GOAL = 21;

enum turnel
{
	center = 40,
	rs = 26, re = 28,
	ls = 50, le = 52,
};

unordered_map<int, int> corner = {
	{5, 26}, {10, 38}, {15, 50}
};
unordered_map<int, int> board_score = {
	{26, 13}, {27, 16}, {28, 19},
	{50, 28}, {51, 27}, {52, 26},
	{38, 22}, {39, 24}, {40, 25}, {41, 30}, {42, 35}, {43, 40}
};
int ans, dice[10], h[4], score[4];
bool visited[53];

int gain_score(int p)
{
	if (p < GOAL) return p * 2;
	if (p == GOAL) return 0;
	return board_score[p];
}
int move(int start, int cnt)
{
	int next = start + cnt;

	// 코너에 진입한 경우
	if (start == 5 || start == 10 || start == 15)
		next = move(corner[start], cnt - 1);
	// 오른 통로
	else if (turnel::rs <= start && start <= turnel::re)
	{
		if (next > turnel::re) next = turnel::center + next - turnel::re - 1;
	}
	// 왼 통로
	else if (turnel::ls <= start && start <= turnel::le)
	{
		if (next > turnel::le) next = turnel::center + next - turnel::le - 1;
	}
    // 종료 지점
	if ((GOAL <= next && next <= GOAL + 4) || (TURNEL_GOAL <= next && next <= TURNEL_GOAL + 4))
		next = GOAL;
	else if (next == TURNEL_GOAL - 1)
		next = GOAL-1;
	return next;
}
void dfs(int n)
{
	if (n == 10)
	{
		ans = max(ans, score[0] + score[1] + score[2] + score[3]);
		return;
	}
	register int i, next, s, pos;
	// 1. 말 4개를 차례대로 진행
	for (i = 0; i < 4; ++i)
	{
		// 완주한 것이 아니면 이동 가능
		if (h[i] != GOAL)
		{
			// 2. 이동
			next = move(h[i], dice[n]);

			// 3. 이동한 위치에 다른 말이 존재
			if (next != GOAL && visited[next]) 
				continue;
			
			pos = h[i];
			visited[pos] = false;
			visited[next] = true;
			h[i] = next;
			s = gain_score(next);
			score[i] += s;
			dfs(n + 1);

			visited[pos] = true;
			visited[next] = false;
			h[i] = pos;
			score[i] -= s;
		}
	}
}

int main()
{
	// freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	register int i;
	for (i = 0; i < 10; ++i)
		cin >> dice[i];
	dfs(0);
	cout << ans;
	return 0;
}

 

통로 이동 부분 때문에 코드가 좀 더럽습니다 ㅠㅠ

끔찍한 하드 코딩이군요