백준 주사위 윷놀이 재도전

1) 배열은 line별로 만드는 것이 아니고 2차원 배열로 하나로 만든다.

2) visit 처리는 배열로 처리하기 힘들다. -> 예외 상황이 너무 많음 이를테면 레인 1의 30위치에서 없어서 이동 가능하다고 생각했으나 레인 2의 30위치가 겹치므로 이동 불가한다던가... 

그래서 check 함수를 따로 만들고 이동하고 자하는 road와 idx를 보낸다. 

같은 road 같은 idx에 윷이 있으면 당연히 못가고

같은 road 같은 idx가 아니더라도 25, 30, 35, 40은 경로가 겹치므로 자신이 25일 때 남도 25이면 못감

근데 30같은 경우는 겹치는 경로 외에도 다른 경로에도 존재하는 수이므로 겹치는 경로의 30임을 명시해줘야함.

이전 경로가 25라던지 하는 방식..

 

3) 어떤 레인에서 도착경로를 넘어서면 죽은것으로 처리. 나머지 상황은 이동

0 레인에 대해서만 경로가 꺾이는거 고려.

 

 

 

#include<iostream>


using namespace std;



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 };

int dice[10];
struct Node {
	int road;
	int idx;
	bool death;
};

Node horse[4];
int maxa;
int result;


bool check(int road, int idx)
{
	for (int i = 0; i < 4; i++)
	{
		if (!horse[i].death && map[horse[i].road][horse[i].idx] != 0)
		{
			if (horse[i].road == road && horse[i].idx == idx)
			{
				return false;
			}
			else if (map[horse[i].road][horse[i].idx] == 25 && map[road][idx] == 25)
			{
				return false;
			}
			else if (map[horse[i].road][horse[i].idx] == 35 && map[road][idx] == 35)
			{
				return false;
			}
			else if (map[horse[i].road][horse[i].idx] == 40 && map[road][idx] == 40)
			{
				return false;
			}
			else if (map[horse[i].road][horse[i].idx] == 30 && map[road][idx] == 30)
			{
				if (map[horse[i].road][horse[i].idx - 1] == 25 && map[road][idx-1] == 25)
				{
					return false;
				}
			}
		}
	}
	return true;

}


void DFS(int cur)
{

	if (cur == 10)
	{

		if (result > maxa)
		{
			maxa = result;
		}
		return;
	}


	for (int i = 0; i < 4; i++)
	{
		if (!horse[i].death)
		{
			int newidx = horse[i].idx + dice[cur];
			int tempidx = horse[i].idx;
			int temproad = horse[i].road;


			if (temproad == 0)
			{
				if (newidx >= maplen[0])
				{
					horse[i].idx = maplen[0];
					horse[i].death = true;
					DFS(cur + 1);
					horse[i].death = false;
					horse[i].idx = tempidx;
				}
				else if (newidx == 5)
				{
					if (check(1, 0))
					{
						horse[i].idx = 0;
						horse[i].road = 1;
						result += map[1][0];
						DFS(cur + 1);
						result -= map[1][0];
						horse[i].idx = tempidx;
						horse[i].road = temproad;

					}
					
				}
				else if (newidx == 10)
				{
					if (check(2, 0))
					{
						horse[i].idx = 0;
						horse[i].road = 2;
						result += map[2][0];
						DFS(cur + 1);
						result -= map[2][0];
						horse[i].idx = tempidx;
						horse[i].road = temproad;

					}

				}
				else if (newidx == 15)
				{
					if (check(3, 0))
					{
						horse[i].idx = 0;
						horse[i].road = 3;
						result += map[3][0];
						DFS(cur + 1);
						result -= map[3][0];
						horse[i].idx = tempidx;
						horse[i].road = temproad;

					}
				}
				else
				{
					if (check(0, newidx))
					{
						horse[i].idx = newidx;
						result += map[0][newidx];
						DFS(cur + 1);
						horse[i].idx = tempidx;
						result -= map[0][newidx];
					}
					
				}
			}
			else if (temproad == 1)
			{
				if (newidx >= maplen[1])
				{
					horse[i].idx = maplen[1];
					horse[i].death = true;
					DFS(cur + 1);
					horse[i].death = false;
					horse[i].idx = tempidx;
				}
				else if (check(1, newidx))
				{
					horse[i].idx = newidx;
					result += map[1][newidx];
					DFS(cur + 1);
					horse[i].idx = tempidx;
					result -= map[1][newidx];
				}
			}
			else if (temproad == 2)
			{
				if (newidx >= maplen[2])
				{
					horse[i].idx = maplen[2];
					horse[i].death = true;
					DFS(cur + 1);
					horse[i].death = false;
					horse[i].idx = tempidx;
				}
				else if (check(2, newidx))
				{
					horse[i].idx = newidx;
					result += map[2][newidx];
					DFS(cur + 1);
					horse[i].idx = tempidx;
					result -= map[2][newidx];
				}
			}
			else if (temproad == 3)
			{
				if (newidx >= maplen[3])
				{
					horse[i].idx = maplen[3];
					horse[i].death = true;
					DFS(cur + 1);
					horse[i].death = false;
					horse[i].idx = tempidx;
				}
				else if (check(3, newidx))
				{
					horse[i].idx = newidx;
					result += map[3][newidx];
					DFS(cur + 1);
					horse[i].idx = tempidx;
					result -= map[3][newidx];
				}

			}


		}
	}

}


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

	for (int i = 0; i < 4; i++)
	{
		horse[i] = { 0,0,0 };
	}
	maxa = -1;
	DFS(0);

	cout << maxa << endl;
}