주사위 윷놀이 C++

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

17825번: 주사위 윷놀이

 

#include <iostream>
#include <vector>

using namespace std;

struct INFO { int loc, way, way_loc, exist; }; // 위치, 길, 길에서 위치, 선택가능여부
//시작 : 0, 도착: 41
INFO horse[4];
int num[10];
int answer = 0;
int w_1[26] = { 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,41,41,41,41,41 };
int w_2[13] = { 10,13,16,19,25,30,35,40,41,41,41,41,41 };
int w_3[12] = { 20,22,24,25,30,35,40,41,41,41,41,41 };
int w_4[13] = { 30,28,27,26,25,30,35,40,41,41,41,41,41 };

void copyhorse(INFO temp[4]) {
	for (int i = 0; i < 4; i++) {
		temp[i] = horse[i];
	}
}

void remakehorse(INFO temp[4]) {
	for (int i = 0; i < 4; i++) {
		horse[i] = temp[i];
	}
}

void dfs(int n,int value) {
	INFO temp[4];
	copyhorse(temp);
	
	if (n == 10) {
		if (answer < value)
			answer = value;
	}

	else {
		for (int i = 0; i < 4; i++) {
			//이동 가능한 말
			if (horse[i].exist == 1) {
				//파랑칸 시작
				if (horse[i].loc == 10) {
					horse[i] = {w_2[num[n]], 2,num[n],1};
				}
				else if (horse[i].loc == 20) {
					horse[i] = {w_3[num[n]], 3, num[n], 1};
				}
				else if (horse[i].loc == 30) {
					if (horse[i].way == 1)
						horse[i] = { w_4[num[n]],4,num[n],1 };
					else if(horse[i].way== 2)
						horse[i] = { w_2[temp[i].way_loc + num[n]],2,temp[i].way_loc + num[n] ,1 };
					else if (horse[i].way == 3)
						horse[i] = { w_3[temp[i].way_loc + num[n]],3,temp[i].way_loc + num[n] ,1 };
					else if(horse[i].way==4)
						horse[i] = { w_4[temp[i].way_loc + num[n]],4,temp[i].way_loc + num[n] ,1 };
				}
				//파랑칸 아닌칸에서 시작
				else {
					if(horse[i].way == 1)
						horse[i] = {w_1[temp[i].way_loc+num[n]],1,temp[i].way_loc+num[n],1};
					else if(horse[i].way==2)
						horse[i] = { w_2[temp[i].way_loc + num[n]],2,temp[i].way_loc + num[n],1 };
					else if(horse[i].way==3)
						horse[i] = { w_3[temp[i].way_loc + num[n]],3,temp[i].way_loc + num[n],1 };
					else if(horse[i].way==4)
						horse[i] = { w_4[temp[i].way_loc + num[n]],4,temp[i].way_loc + num[n],1 };
				}

				//이동 끝
				//도착점 도착
				if (horse[i].loc == 41) {
					horse[i].exist = 0;
					dfs(n + 1, value);
				}
				else {
					bool flag = false;
					//도착점에 말이 있음
					for (int k = 0; k < 4; k++) {
						if (k == i) continue;

						//if (horse[i].loc == temp[k].loc && horse[i].way == temp[k].way && horse[i].way_loc == temp[k].way_loc && horse[i].exist == temp[k].exist) {

						if (horse[i].loc == temp[k].loc ) {
							if (horse[i].loc == 22 || horse[i].loc == 24 || horse[i].loc == 26 || horse[i].loc == 28) {
								if (horse[i].way == temp[k].way) {
									flag = true;
									break;
								}
							}
							else if (horse[i].loc == 30) {
								if (horse[i].way != 1 && temp[k].way != 1) {
									flag = true;
									break;
								}
								else if (horse[i].way == 1 && temp[k].way == 1) {
									flag = true;
									break;
								}
							}
							else {
								flag = true;
								break;
							}
						}
					}
					if (flag == false) 
						dfs(n + 1, value + horse[i].loc);

				}
				horse[i] = temp[i];
			}
		}
	}
	remakehorse(temp);
}

int main(void) {

	for (int i = 0; i < 10; i++) {
		cin >> num[i];
	}
	
	for (int i = 0; i < 4; i++) {
		horse[i] = { 0, 1, 0, 1 };
	}
	dfs(0, 0);
	cout << answer << endl;
	return 0;
}