[백준 17825] 주사위 윷놀이 (C++)

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

17825번: 주사위 윷놀이

1. 주의할 점

- 이동하려는 칸에 다른 플레이어의 말이 있으면 그 판은 무효로 한다

- 1번이 10번 다 이동하는거랑 2~4번이 10번 다 이동하는것은 같다. 이것을 따로 처리해주자(스터디원 曰: 실제 시험에서는 이거 처리 안하면 TLE로 통과 못했다고 한다)

- 윷놀이 점수판을 따로 배열로 만든다

 

2. 구현

- 주사위의 정보를 입력받고 DFS()를 수행하며 어떤 플레이어가 움직일건지 정한다

- DFS()를 수행하면서 위의 빨간글씨 조건을 처리하기 위해 For문에선 i: 0~Min(cnt+1,4)로 설정했다. 그 이유는 잘 생각해보자

- Cnt가 10이 되면 Play() 함수를 수행하여 윷놀이 게임을 한다

- 윷놀이를 수행하며 꺽이는 부분, 중앙에서 위로 올라가는 부분, 40점에 도착, 40점에서 도착지점까지 잘 고려하여 짠다(노가다라서 방식은 여러가지가 있을 수 있다). 단, 말이 도착지점이 아닌곳에서 겹치면 그 게임은 즉시 종료하고 점수 비교 또한 하지 않는다

 

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

struct info {
	int lev, idx;
};
info tmp;
vector<int> v;
int number[10], result = 0;
info player[4];

void play() {
	int t_result = 0;
	for (int i = 0; i < 4; i++) {
		player[i].idx = 0;
		player[i].lev = 0;
	}
	bool finish = true;
	int nl, nidx, next;		//다음 층, 다음 위치
	for (int i = 0; i < v.size(); i++) {
		int dice = number[i];
		int pl = player[v[i]].lev;
		int pidx = player[v[i]].idx;
		if (pl == 5 && pidx == 1) continue;		//도착지점
		next = dice + pidx;
		if (pl == 0) {
			if (next == 5) {
				nl = 1;
				nidx = 0;
			}
			else if (next == 10) {
				nl = 2;
				nidx = 0;
			}
			else if (next == 15) {
				nl = 3;
				nidx = 0;
			}
			else if (next == 20) {
				nl = 5;
				nidx = 0;
			}
			else if (next > 20) {
				nl = 5;
				nidx = 1;
			}
			else {
				nl = pl;
				nidx = next;
			}
		}
		else if (pl == 1 || pl==3) {
			if (next < 4) {
				nl = pl;
				nidx = next;
			}
			else if (4 <= next && next <= 6) {
				nl = 4;
				nidx = next - 4;
			}
			else if (next == 7) {
				nl = 5;
				nidx = 0;
			}
			else if (next == 8) {		//도착지점
				player[v[i]].idx = 1;
				player[v[i]].lev = 5;
				continue;
			}
		}
		else if (pl == 2) {
			if (next < 3) {
				nl = pl;
				nidx = next;
			}
			else if (3 <= next && next <= 5) {
				nl = 4;
				nidx = next - 3;
			}
			else if (next == 6) {
				nl = 5;
				nidx = 0;
			}
			else if (next == 7) {
				player[v[i]].idx = 1;
				player[v[i]].lev = 5;
				continue;
			}
		}
		else if (pl == 4) {
			if (next < 3) {
				nl = pl;
				nidx = next;
			}
			else if (next == 3) {
				nl = 5;
				nidx = 0;
			}
			else if (next > 3) {
				player[v[i]].idx = 1;
				player[v[i]].lev = 5;
				continue;
			}
		}
		else if (pl == 5) {		//무조건 도착지점으로 가서 점수 계산 필요x
			player[v[i]].idx = 1;
			player[v[i]].lev = 5;
			continue;			
		}
		
		for (int k = 0; k < 4; k++) {
			if (k == v[i]) continue;
			if (player[k].idx == nidx && player[k].lev == nl) {
				finish = false;
				break;
			}
		}
		if (!finish) break;
		//자리 체인지
		player[v[i]].lev = nl;
		player[v[i]].idx = nidx;
		//값 더하기
		t_result += arr[nl][nidx];		
	}
	if (finish) 	result = max(result, t_result);	
}

void dfs(int cnt) {
	if (cnt == 10) {
		play();
		return;
	}
	for (int i = 0; i < min(4, cnt+1); i++) {
		v.push_back(i);
		dfs(cnt + 1);
		v.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for (int i = 0; i < 10; i++)
		cin >> number[i];
	dfs(0);
	cout << result;
	return 0;
}