백준 17825번 주사위 윷놀이

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

17825번: 주사위 윷놀이

 

 

 

 

 

<접근방법>

완전 탐색 문제입니다.

백트래킹으로 순열을 구현하여 시뮬레이션 하면 됩니다.

 

윷놀이판의 저장 방법이나 윷놀이판의 순회 방법을 결정하는 것이 핵심이었다고 생각합니다.

 

저는 파란색 칸이 5로 나누어 떨어지는 점을 이용하여 구현하였습니다.

다른 분의 코드를 참고해보니 그냥 일차원 배열에 모두 저장하고 인덱스 혹은 방향을 조절해주는 것이

훨씬 쉬워보입니다.

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

struct point {
	int y, x;
	bool suc;
};

int s[10], a[10];
int map[7][22];
int res;

void map_set() {
	int tmp2[8] = {10, 13, 16, 19, 25};
	int tmp4[7] = {20, 22, 24, 25};
	int tmp5[4] = {25, 30, 35, 40};
	int tmp6[8] = {30, 28, 27, 26, 25};

	map[0][0] = 0;
	for (int j = 1; j < 21; j++) {
		map[0][j] = map[0][j - 1] + 2;
	}
	
	int j = 0;
	for (int i = 0; i < 21; i++) {
		if (i < 16) {
			map[2][i] = 0;
		}
		else {
			map[2][i] = tmp2[j++];
		}
	}

	j = 0;
	for (int i = 0; i < 21; i++) {
		if (i < 17) {
			map[4][i] = 0;
		}
		else {
			map[4][i] = tmp4[j++];
		}
	}

	j = 0;
	for (int i = 0; i < 21; i++) {
		if (i < 17) {
			map[5][i] = 0;
		}
		else {
			map[5][i] = tmp5[j++];
		}
	}

	j = 0;
	for (int i = 0; i < 21; i++) {
		if (i < 16) {
			map[6][i] = 0;
		}
		else {
			map[6][i] = tmp6[j++];
		}
	}
}

int simul() {
	bool visit[7][22] = {false, };
	int sum = 0;
	point h[4];
	for (int i = 0; i < 4; i++) {
		h[i].y = 0; h[i].x = 0; h[i].suc = false;
	}

	for (int z = 0; z < 10; z++) {
		int y = h[s[z]].y;
		int x = h[s[z]].x;
		int move = a[z];

		if (h[s[z]].suc) continue;
		visit[y][x] = false;
		if (map[y][x] == 40) {
			visit[0][x] = false;
			visit[5][x] = false;
		}

		if (map[y][x] % 5 == 0 && y == 0 && x != 0) {
			y = map[y][x] / 5;
			if (y == 2) {
				x = 16;
			}
			else if (y == 4) {
				x = 17;
			}
			else if (y == 6) {
				x = 16;
			}
		}

		while (move--) {
			x++;

			if (map[y][x] == 25) {
				y = map[y][x] / 5;
				x = 17;
			}

			if (x >= 21) {
				h[s[z]].suc = true;
				break;
			}
		}
		
		if (!h[s[z]].suc) {
			if (visit[y][x]) return 0;

			sum += map[y][x];
			visit[y][x] = true;
			if (map[y][x] == 40) {
				visit[0][x] = true;
				visit[5][x] = true;
			}
			h[s[z]].y = y;
			h[s[z]].x = x;
		}
	}
	return sum;
}

void dfs(int dep) {
	if (dep == 10) {
		res = max(res, simul());
		return;
	}
	for (int i = 0; i < 4; i++) {
		s[dep] = i;
		dfs(dep + 1);
	}
}


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

	dfs(0);
	cout << res << '\n';
	return 0;
}