백준, boj ) 17825 주사위 윷놀이 (C++)

1. 문제 링크

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

17825번: 주사위 윷놀이

2. 문제 개요

 말 4개를 갖고 주사위를 10번 굴려서 얻을 수 있는 점수중 가장 큰 점수 구하기.

단, 주사위 값을 모두 알고 있음.

 

 

3. 문제 힌트

모든 경우의 수를 조사하기. 맵은 분할해서 배열로 표현했음.

각 조건에 유의하며 풀기.

조건 속에는 '도착한 말은 움직일 수 없다', '말 위에 말을 놓을 수 없다.'와 같은 내용이 있는데,

이러한 조건을 위배하면 다음 경우의 수로 넘어가기.

 

 

4. 문제 풀이

 (1) 주사위 값을 알고 있으니 몇 번째에 어느 말을 옮기느냐가 관건.

즉, 모든 경우의 수를 조사하면 값을 알 수 있음. ->DFS

여기서 속도를 높이고 싶으면 backtracking을 하면 될 것 같다.

 

(2) 윷놀이 판을 어떻게 코드로 나타내는지의 문제.

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

각 색깔별로 배열을 만들어서 구현하였다.

그래서 [4][22]의 배열로 맵을 만들었고, 시작과 도착지점은 '0'점으로 구현하였다.

각각의 길을 첫 번째 index로, 그 길에서 몇 번째 칸에 있는지를 2번째 index로 표현하였다.

 

예를 들면, 파란색 칸인 '10'에 도착했다고 하자. 첫 번째 시작은 검은색 길(map [0][0])에서 시작한다.

그럼 map[0][5]에 도착하는데 이 칸이 파란색 칸인지 구별하고 map[4][0]으로 이동한다. ( 5번 문항의 코드에서는 1번 index의 순서가 다름)

 

이러한 자료구조 및 변수 표현을 기반으로 흐름을 적어보면,

 

움직일 수 있는 말인가? (이미 도착했는지) -> NO return

움직이고, 도착 칸을 초과하여 이동했다면 도착 칸에 두기.

점수를 더하기.

파란 칸을 밟고 있다면 길 변경하기. (ex. 검은색 -> 갈색)

도착 칸이 아닌 다른 칸에서 또 다른 말을 만난다면? -> YES return.

반복.

 

과같은 흐름을 가진다.

 

그러나 이런 식으로 맵을 구현 하면 검은색을 제외한 3개의 배열에서, 도착 - 40 - 35 - 30 - 25 이 부분이 모호해진다.

왜냐하면 말이 놓여 있는 칸에는 또 놓을 수 없기 때문에 이미 말이 놓여있는지 검사하는 부분이 필요하기 때문이다.

말을 놓을 때 점수가 같은 다른 말이 있는지 확인해야 하고, 보라색의 30점과 같은 경우에는 2개가 있어서 모호하다.

또한 갈색의 30점과 보라색의 첫 번째(가장 오른쪽)의 30점과 모호하다. (연두색의 30점과 보라색의 30점도 모호함. 다른 색도 다 동일.)

 

이 부분을 해결하기 위해

점수가 같은지 -> 같은 길에 있는지? -> 도착 ~ 25점 부근에서의 중복인지 검사하여 문제를 해결했다.

이 부분에서 많은 시간을 잡아먹었다..

 

 

5. 코드

#include <iostream>
#include <algorithm>
using namespace std;
//bruteforce  , backtracking
int map[4][22] = { 
	{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,0},
{10,13,16,19,25,30,35,40,0},
{20,22,24,25,30,35,40,0},
{30,28,27,26,25,30,35,40,0} 
};
int maplen[4] = { 21,8,7,8 };

struct node {
	int roadnum;	//몇번째 길
	int location;	//길에서 몇번째 칸에 있는지
	bool arrived;
};

int dice[10];
int maxscore = -1;
int order[10];

bool isthereahorse(node horse[4], int n)
{
	//마지막칸, 시작칸 제외 n번째 말은 이미 이동한 상태
	for (int i = 0; i < 4; ++i)
	{
		if (i != n)
		{
			if (map[horse[n].roadnum][horse[n].location] == map[horse[i].roadnum][horse[i].location])
			{
				if (horse[i].roadnum == horse[n].roadnum)
				{
					return true;
				}
				else
				{
					if (maplen[horse[n].roadnum] - 4 <= horse[n].location && maplen[horse[i].roadnum] - 4 <= horse[i].location)
						return true;
					else
						return false;
				}
				
			}
		}
	}
	return false;
	
}
bool cango(node horse[4] , int n)
{
	if (horse[n].roadnum == 0 && horse[n].location >= maplen[0])
	{
		return false;
	}
	else if (horse[n].roadnum == 1 && horse[n].location >= maplen[1])
	{
		return false;
	}
	else if (horse[n].roadnum == 2 && horse[n].location >= maplen[2])
	{
		return false;
	}
	else if (horse[n].roadnum == 3 && horse[n].location >= maplen[3])
	{
		return false;
	}
	return true;
}
int isblue(node horse[4],int n)
{
	//0번 길에서
	if (horse[n].roadnum == 0)
	{
		if (horse[n].location == 5)
		{
			return 1;
		}
		else if (horse[n].location == 10)
		{
			return 2;
		}
		else if (horse[n].location == 15)
		{
			return 3;
		}
		else
		{
			return -1;
		}
	}
	else
	{
		return -1;
	}
}

void dfs(int depth)
{
	if (depth == 10)
	{
		//여기서 최대값
		node horse[4] = { 0 };
		int score = 0;

		for (int i = 0; i < 10; ++i)
		{
			//이동시켜보기
			if (cango(horse, order[i]))
			{
				//말이 놓여져있는지도 확인
				horse[order[i]].location += dice[i];

				//끝에 도착했는지 확인
				if (!cango(horse, order[i]))
				{
					horse[order[i]].arrived = true;	//location 끝으로 고정시켰음.
					horse[order[i]].location = maplen[horse[order[i]].roadnum];
				}
				
				
				//이동을 끝마쳤으니 점수에 더함.
				score += map[horse[order[i]].roadnum][horse[order[i]].location];

				//파란색이면 경로 변경시켜주기
				int changeroad = isblue(horse, order[i]);

				if (changeroad == 1 || changeroad == 2 || changeroad == 3)
				{
					horse[order[i]].roadnum = changeroad;
					horse[order[i]].location = 0;
				}

				//도착안했고 말이 중복된 위치에 있는지
				if (!horse[order[i]].arrived && isthereahorse(horse, order[i]))
					return;
			}
			else
				return;
		}

		if (maxscore < score)
			maxscore = score;
		return;
	}
	
	for (int num = 0; num < 4; ++num)
	{
		order[depth] = num;
		dfs(depth + 1);
	}
	
	return;
}

int main()
{
	for (int i = 0; i < 10; ++i)
		cin >> dice[i];


	dfs(0);

	cout << maxscore;
	return 0;
}

Backtracking은 사용하지 않았습니다.

시간이 있다면 Backtracking으로도 구현할 예정입니다.

 

6. 결과 사진

지적, 댓글 언제나 환영입니다~