[BOJ]백준 17825번: 주사위 윷놀이 풀이 및 반례

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

나를 아주아주 괴롭혔던 주사위 윷놀이 문제이다.....

처음에 봤을 때는 저 ㄱㅓ지같은 문제는 어떻게 풀어야 하지.....?? 맵을 링크드리스트로 구현해야 하나...?? 라는 생각을 했었는데

 

잘 보면 윷놀이의 코스는 4가지로 나뉜다는걸 알 수 있다

그리고 각 코스의 공통점은, 10/20/30을 밟을 경우 해당 번호의 코스로 이동한다는 것!!

또한 코스의 이동은 0번에서 1,2,3번으로의 이동밖에 없다

 

예를 들어 0번의 16을 밟고 있다가 2칸을 이동해서 20으로 간다면, 코스는 2번으로 바뀐다

그래서 위와 같이 처음에 설계를 할 수 있었다

16, 22, 24, 26, 28의 경우에는 맵 상에 두 개가 존재하기 때문에 코스와 위치 또한 일치해야 한다!

그리고...... 30을 처리해주는게 핵심이다

30은 모든 코스에 존재하고, 심지어 3번 코스에서는 2번이나 밟을 위험이 있다 !!!!

그렇기에 신경써줘야 할 것은 코스를 바꿔주는 시점, 그리고 기점이 되는 위치이ㄷㅏ 😥

나의 경우에는

- 현재 주사위 눈에 따른 next 좌표 계산(맵의 범위를 초과하면 도착지점으로 이동)

- 해당 좌표가 이동 가능한가?(다른 말들이 그 위치에 있나)

- 코스를 바꿔줘야 한다면 바꾸기

를 중심으로, 백트래킹 구현을 해주었다

#include <cstdio>
int map[][24] = {
	{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40},
	{0,2,4,6,8,10,13,16,19,25,30,35,40},	//12
	{0,2,4,6,8,10,12,14,16,18,20,22,24,25,30,35,40},
	{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,28,27,26,25,30,35,40}
};
int loc[4], road[4], dice[10], ans, end[4] = { 21,13,17,23 };
bool canMove(int cur) {
	int n = map[road[cur]][loc[cur]];
	if (!n)return 1;
	for (int i = 0; i < 4; i++) {
		if (i == cur)continue;
		if (map[road[i]][loc[i]] != n)continue;
		if (n == 16 || n == 22 || n == 24 || n == 26 || n == 28) {
			if ((loc[i] == loc[cur])
				&& (road[i] == road[cur]))return 0;
		}
		else if (n == 30) {
			if (road[cur] == 0 && loc[cur] == 15) {
				if (loc[i] == 15)return 0;
			}
			else if (road[cur] == 3 && loc[cur] == 15) {
				if (road[i] == 3 && loc[i] == 15)return 0;
			}
			else {
				if (road[i] == 3 && loc[i] == 15)continue;
				return 0;
			}

		}else return 0;
	}
	return 1;
}
void func(int dep, int score) {
	if (dep >= 10) {
		if (score > ans)ans = score;
		return;
	}

	for (int i = 0; i < 4; i++) {
		if ((loc[i] > 0) && !map[road[i]][loc[i]])continue;
		if (i > dep)continue;
		int pl = loc[i], pr = road[i];
		loc[i] += dice[dep];

		if (loc[i] > end[road[i]])loc[i] = end[road[i]];

		int next = map[road[i]][loc[i]];

		if (canMove(i)) {
			if (next == 10 || next == 20 ||
				(road[i] == 0 && next == 30))road[i] = next / 10;
			func(dep + 1, score + next);
		}

		loc[i] = pl; road[i] = pr;
	}
}
int main() {
	for (int i = 0; i < 10; i++)scanf("%d", &dice[i]);
	func(0, 0);
	printf("%d", ans);
	return 0;
}

코테보기 전에 모노미노도미노랑 주사위윷놀이만 3번씩 풀고 들가면 도움이 될 듯 하당 ^^

 

반례모음

5 5 5 5 5 1 1 1 1 1
ans 167

5 5 5 5 5 2 2 2 2 2
ans 160

5 5 5 5 5 2 2 1 3 3
ans 161

 

1 2 3 4 5 5 4 3 2 1

ans 207

 

1 4 5 5 4 3 2 1 2 3 

ans 224

 

1 4 5 5 2 1 2 3 4 3  

ans 211

 

1 4 5 2 3 4 3 5 2 1

ans 230

 

1 1 1 1 1 1 1 1 1 1

ans 133

 

1 1 1 1 4 4 1 1 1 1

ans 172

 

2 2 2 2 2 2 2 2 2 2

ans 166

 

2 3 2 3 2 3 2 3 2 3

ans 186