주사위 윷놀이 - 17825

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

17825번: 주사위 윷놀이

 

코드 : 

#include <iostream>
#include <vector>

using namespace std;

int result = 0;
int indexArr[33][2] = { 0 }; // 이동 인덱스 
int vArr[33] = { 0 }; // 값
bool check[4] = { false };
int pos[4] = { 0 }; // 말의 위치

void solution(int count, int* move, int max)
{
	if (count == 10)
	{
		if (max > result)
		{
			result = max;
		}
		return;
	}

	//말 갯수만큼 루프
	for (int c = 0; c < 4; c++)
	{
		int si = pos[c]; // 각 말별로 위치한 지점부터 시작

		//이미 도착한 말 체크
		if (check[c])
			continue;
		
		int addvalue = 0;
		//다른 길
		bool other = false;
		if (si == 5 || si == 10 || si == 15)
		{
			other = true;
		}
		int k = move[count];
		for (int i = 0; i < k; i++)
		{
			if (other)
			{
				other = false;
				si = indexArr[si][1];
			}
			else
			{
				si = indexArr[si][0];
			}
			if (si == 21)
				break;
		}
		//다른 말이 이미 위치해있는 경우 단 종료지점은 예외
		bool already = false;
		for (int j = 0; j < 4; j++)
		{
			if (si == pos[j] && si != 21)
			{
				already = true;
				continue;
			}
		}
		if (already) continue;

		int temp = pos[c];
		pos[c] = si;
		addvalue += vArr[si];

		if (si == 21)
		{
			check[c] = true;
		}
		solution(count + 1, move, max + addvalue);
		if (check[c])
		{
			check[c] = false;
		}
		pos[c] = temp; // 이동한것 원복
	}

}


int main()
{
	int move[10] = { 0 };

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

	// lookup Table
	for (int i = 0; i <= 20; i++)
	{
		indexArr[i][0] = i + 1;
	}

	indexArr[5][1] = 22;
	indexArr[10][1] = 26;
	indexArr[15][1] = 28;

	indexArr[22][0] = 23;
	indexArr[23][0] = 24;
	indexArr[24][0] = 25;

	indexArr[26][0] = 27;
	indexArr[27][0] = 25;

	indexArr[28][0] = 29;
	indexArr[29][0] = 30;
	indexArr[30][0] = 25;

	indexArr[25][0] = 31;
	indexArr[31][0] = 32;
	indexArr[32][0] = 20;

	// 값 저장
	for (int i = 1; i <= 20; i++)
	{
		vArr[i] = i * 2;
	}
	vArr[22] = 13;
	vArr[23] = 16;
	vArr[24] = 19;
	vArr[25] = 25;

	vArr[28] = 28;
	vArr[29] = 27;
	vArr[30] = 26;

	vArr[26] = 22;
	vArr[27] = 24;

	vArr[31] = 30;
	vArr[32] = 35;

	solution(0, move, 0);

	cout << result << "\n";
	return 0;
}

 어렵다.. 아직도 부족한게 너무 많다...

크게보면

1. 윷놀이 판을 배열에 맵핑하는 방법

2. DFS를 사용하여 모든 말에 대한 경우의 수 구하기

이렇게 2가지로 볼 수 있었다...