[백준] 17825번 - 주사위 윷놀이 / C++

문제

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

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

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

 

입력

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

 

출력

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

 

코드

#include <iostream>
#include <vector>

using namespace std;

struct pos
{
	int r;
	int c;
	bool finish;	// 도착했는지

	void init(int r, int c, bool finish)
	{
		this->r = r;
		this->c = c;
		this->finish = finish;
	}
};

vector< vector<int> > board;
vector<int> turn;
int max_score;

// 게임 보드 초기화
void init_board()
{
	int i;
	int line10[] = {13, 16, 19};
	int line20[] = {22, 24};
	int line30[] = {28, 27, 26};
	int line25[] = {25, 30, 35};

	board.resize(5);
	for (i = 0; i < 21; i++)
		board[0].push_back(i * 2);
	board[0].push_back(0);
	for (i = 0; i < 3; i++)
		board[1].push_back(line10[i]);
	for (i = 0; i < 2; i++)
		board[2].push_back(line20[i]);
	for (i = 0; i < 3; i++)
		board[3].push_back(line30[i]);
	for (i = 0; i < 3; i++)
		board[4].push_back(line25[i]);
}

// 말을 현재 위치에서 cnt칸 이동시킨 좌표를 리턴
pos move(int cnt, pos curr)
{
	int i;
	pos next = curr;

	// 파란색 칸에서 이동을 시작하는 경우 파란색 화살표를 따라 이동
	if (next.c == 5 || next.c == 10 || next.c == 15)
	{
		next.r = next.c / 5;
		next.c = 0;
		cnt--;
	}
	for (i = 0; i < cnt; i++)
	{
		// 해당 라인의 마지막 칸인 경우
		if (++next.c == board[next.r].size())
		{
			// 도착 칸인 경우
			if (next.r == 0)
			{
				next.finish = true;
				return next;
			}
			// 19, 24, 26 -> 25로 이동해야 하는 경우
			else if (next.r > 0 && next.r < 4)
			{
				next.r = 4;
				next.c = 0;
			}
			// 35 -> 40으로 이동
			else
			{
				next.r = 0;
				next.c = 20;
			}
		}
	}
	return next;
}

// 말이 이동하려는 칸에 다른 말이 있는지 확인
bool exist(int num, vector<pos> &piece)
{
	int i;

	for (i = 0; i < 4; i++)
	{
		// 이동하려는 말이거나 도착한 말이면 패스
		if (i == num || piece[i].finish)
			continue;
		if (piece[i].r == piece[num].r && piece[i].c == piece[num].c)
			return true;
	}
	return false;
}

// 턴 t에서 움직일 말을 선택하여 다음 dfs 수행
void dfs(int t, int total_score, vector<pos> piece)
{
	int i, score;
	pos curr, next;
	vector<pos> new_piece;

	// 모든 턴을 완료했으면 최대 점수 갱신
	if (t == 10)
	{
		max_score = max(max_score, total_score);
		return;
	}
	// i번 말을 차례대로 선택해 봄
	for (i = 0; i < 4; i++)
	{
		// 이미 도착한 말은 이동할 수 없음
		if (piece[i].finish)
			continue;
		new_piece.assign(piece.begin(), piece.end());
		new_piece[i] = move(turn[t], new_piece[i]);
		if (exist(i, new_piece))
			continue;
		score = board[new_piece[i].r][new_piece[i].c];
		dfs(t + 1, total_score + score, new_piece);
	}
}

int main()
{
	int i, num;
	pos p;
	vector<pos> piece;

	for (i = 0; i < 10; i++)
	{
		cin >> num;
		turn.push_back(num);
	}
	init_board();
	p.init(0, 0, false);
	for (i = 0; i < 4; i++)
	{
		piece.push_back(p);
	}
	dfs(0, 0, piece);
	cout << max_score << endl;
	return 0;
}

 

게임 보드를 다음과 같이 변형하여 나타내었다.

시작 칸과 도착 칸의 값은 0이다. 각 행은 아래에 표시된 것처럼 하나의 라인을 나타낸다. 10이 적힌 칸에서 파란색 화살표를 따르면 1번 행, 20이 적힌 칸에서 파란색 화살표를 따르면 2번행, 30이 적힌 칸에서 파란색 화살표를 따르면 3번 행으로 이동한다. 1, 2, 3번 행의 마지막 칸에 이르면 25가 적힌 칸으로 이동해야 하므로 4번 행으로 이동한다. 4번 행의 마지막 칸에 이르면 다시 0번 행의 40이 적힌 칸으로 이동한다.

 

이제 만들어진 보드와 dfs를 사용해 모든 경우를 확인한다. 이때 말의 위치가 계속 변하기 때문에 새로 할당하여 사용한다.

 

링크

17825번: 주사위 윷놀이

inbdni/Baekjoon