[백준/c++] 17825 주사위 윷놀이

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 1) 말 4개가 있다.
• 말은 게임판에 2) 그려진 화살표의 방향대로만 이동할 수 있다. 말이 3) 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 4) 주사위에 나온 수와 관계 없이 이동을 마친다.
• 5) 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 6) 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다.   7) 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다  8) 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력

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

출력

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

 

구현해야할 조건

말 4개가 존재를 하는데, 이동하면서 최대의 값을 뽑아내는 백트래킹이다. 알고리즘 자체는 생각보다 가볍지만, 그래프를 만드는데 시간이 필요하다. 그래프를 직접 만들어서 지정해줘야하기 때문이다.

백트랙킹에서는 1111111111(말의 번호) ~ 4444444444(말의번호) 이런 가지수로 전부 탐색하면 되지만, 그 안에 조건이 있는데 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야한다. 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야한다. 빨간색 화살표 지정을 꼼꼼히 해야한다. 하지 않으면 너어어어어어어무 복잡해지고 힘들어 진다. 말이 있는 칸으로 이동해서는 안된다. 그럼 다른 말을 움직여야 한다. 이점을 유의하면서 풀자!

 

code

 

#include<iostream>
#include<vector>

using namespace std;

int dice[10];
int horse[4];

int map[35];
int Turn_Blue[35];
int score[35];
bool check[35];

int res = 0;

void DFS(int cnt, int sum)
{
	if(cnt == 10)
	{
		if(sum > res)
			res = sum;
			
		return;
	}
	
	for(int i = 0; i < 4; i++)
	{
		int before = horse[i]; // 이전 말의 위치 
		int now = before; // 현재 위치로 바꿔주고 
		int move = dice[cnt]; // 몇번째 주사위 위치
		
		if(Turn_Blue[now] > 0) // 파란 화살표로 가는  
		{
			now = Turn_Blue[now];
			move -= 1; // 파란색칸으로만 이동을 했다. 
		} 
		
		while(move--)
		{
			now = map[now]; // 이동하기 위해서 i+1로 지정해뒀고 
		}
		
		if(now != 21 && check[now] == true) // 종착지가 아니고, 말이 있는 곳이라면?
			continue;
			
		check[before] = false;
		check[now] = true;
		horse[i] = now;
		
		DFS(cnt+1, sum + score[now]);
		
		check[before] = true;
		check[now] = false;
		horse[i] = before; 
	}
}

int main()
{
	for(int i = 0; i < 21; i++)
		map[i] = i + 1; // 1~20 (빨간 발판) 이동을 해야하기 때문에 한칸씩 전진하는 값으로 넣어 주었다. 배열index가 아니라 한칸이야!
		
	map[21] = 21; // 도착 위치 (End)
	
	for(int i = 22; i < 27; i++)
		map[i] = i + 1; // 22 ~ 26까지 27까지 안한 이유는 27 다음은 20이기 때문에, 이런점을 특히 주의해야한다.
		
	map[27] = 20; map[28] = 29; map[29] = 30; // map[27] = 20 도착위치
	map[30] = 25; map[31] = 32; map[32] = 25; // map[30] = 25인것은 map[30]에서 한칸 더 나가면 socre 25인 칸으로 이동하기 때문에
	
	Turn_Blue[5] = 22; Turn_Blue[10] = 31; Turn_Blue[15] = 28;
	Turn_Blue[25] = 26; // 파란색 방향으로 이동하는 칸에 위치해 있다! 5,10,15,25는 파란칸은 아니지만 여기에 떨어지면 map[26]으로 이동을 해야한다.
	
	for(int i = 0; i < 21; i++)
		score[i] = i * 2; // 0~20번째까지 
		
	score[22] = 13; score[23] = 16; score[24] = 19;
	score[25] = 25; score[26] = 30; score[27] = 35;
	score[28] = 28; score[29] = 27; score[30] = 26;
	score[31] = 22; score[32] = 24; // 파란색칸으로 이동해서 진행하는 부분
 	
	for(int i = 0; i < 10; i++)
		cin >> dice[i];
		
	DFS(0,0);
	
	cout << res << "\n";
	
	return 0;
}