백준 - 주사위 윷높이 (17825 번)

백준 - 주사위 윷높이 (17825 번)

풀 때 몸상태가 좋지 않아서 굉장히 스트레스 받으면서 풀었다..

규칙은 다음과 같다.
위와 같은 판에서 4개의 말이 움직인다.
이 때 1~5의 거리를 가지고 이동할 수 있고, 10, 20, 30에서 시작하면 파랑색 화살표를 따라서 움직여야 한다(우리가 흔히 아는 윷놀이).
단, 말이 이미 존재하는 곳으로 움직이려하면 안된다. (이 조건때문에 엄청 틀림 ㅜ)
이 때, 말이 밟고있는 윷놀이 판 숫자만큼 점수를 획득할 수 있고, 도착지점을 넘어간 말은 다시 못쓴다.

일단 푸는 방식은 크게 DFS + 시뮬레이션이다.

미리 Input으로 10번의 숫자가 들어오고, 해당 숫자만큼 움직일 수 있는 데 어떤 말을 움직일지는 DFS를 통해서 정하는 것이다.

(1 1 1 1 1 ... 1), (1 1 1 1 1 ... 2) ... (1 2 3 1 4 ... 3) ... (4 4 4 4 4 ... 4) 의 형태의 DFS를 얻을 수 있다.

DFS를 돌 때, 각 말의 점수를 누적해서 더해주고, 10번의 DFS가 끝나면 이를 다 더해서 최대값을 갱신해주면 된다.

단, 말이 움직일 때 이미 말이 존재하는 곳으론 못움직이기 때문에 이를 주의깊게 체크해줘야 한다.
1차원 배열로 처리하려고 한다면 30, 22, 24, 26, 28의 숫자가 판에 2개 이상 존재하는 것을 주의해줘야 한다.

2차원 배열로 맵을 만들어도 똑같다. 중복되는 값을 가질 수 있는 모든 위치에 대해서 말이 존재하는지 여부를 체크해줘야 한다.

코드는 아래와 같다.

#include <cstdio>
#include <iostream>

using namespace std;

typedef struct __horse_info {
	int row;
	int col;
	int score;
	int dir;
	bool finish;
} horse_info;

int b[16];
int map[32][32];
int horse_map[32][32];

horse_info horse[4];

int answer = 0;

void init_map()
{
	for (int i = 0; i < 21; i++)
		map[i][0] = i * 2;
	map[21][0] = 0;

	map[5][1] = 13; map[5][2] = 16; map[5][3] = 19; map[5][4] = 25;
	map[5][5] = 30; map[5][6] = 35; map[5][7] = 40; map[5][8] = 0;

	map[10][1] = 22; map[10][2] = 24; map[10][3] = 25;
	map[10][4] = 30; map[10][5] = 35; map[10][6] = 40; map[10][7] = 0;

	map[15][1] = 28; map[15][2] = 27; map[15][3] = 26; map[15][4] = 25;
	map[15][5] = 30; map[15][6] = 35; map[15][7] = 40; map[15][8] = 0;
}

void bfs(int n, int depth)
{
	if (depth == 10) {
		int result = 0;
		for (int i = 0; i < 4; i++)
			result += horse[i].score;
		answer = max(answer, result);
		return;
	}

	for (int i = 0; i < n; i++) {
		if (horse[i].finish)
			continue;

		int row = horse[i].row;
		int col = horse[i].col;
		int dir = horse[i].dir;
		int score = horse[i].score;
		bool finish = horse[i].finish;

		int nrow = horse[i].row;
		int ncol = horse[i].col;
		if (horse[i].dir == 0)
			nrow = nrow + b[depth];
		else
			ncol = ncol + b[depth];

		if (nrow >= 21)
			horse[i].finish = true;
		else if (nrow == 5 && ncol >= 8)
			horse[i].finish = true;
		else if (nrow == 10 && ncol >= 7)
			horse[i].finish = true;
		else if (nrow == 15 && ncol >= 8)
			horse[i].finish = true;

		if (!horse[i].finish) {
			if (map[nrow][ncol] == 25) {
				if (horse_map[5][4] == 1 || horse_map[10][3] == 1 || horse_map[15][4] == 1)
					continue;
			}
			else if (map[nrow][ncol] == 30 && ncol != 0) {
				if (horse_map[5][5] == 1 || horse_map[10][4] == 1 || horse_map[15][5] == 1)
					continue;
			}
			else if (map[nrow][ncol] == 35) {
				if (horse_map[5][6] == 1 || horse_map[10][5] == 1 || horse_map[15][6] == 1)
					continue;
			}
			else if (map[nrow][ncol] == 40) {
				if (horse_map[5][7] == 1 || horse_map[10][6] == 1 || horse_map[15][7] == 1 || horse_map[20][0] == 1)
					continue;
			}
			else {
				if (horse_map[nrow][ncol] == 1)
					continue;
			}
		}
		horse_map[row][col] = 0;
		horse_map[nrow][ncol] = 1;

		if (nrow == 5 || nrow == 10 || nrow == 15)
			horse[i].dir = 1;
		horse[i].row = nrow;
		horse[i].col = ncol;
		horse[i].score += map[nrow][ncol];

		bfs(n, depth + 1);

		horse_map[row][col] = 1;
		horse_map[nrow][ncol] = 0;
		horse[i].row = row;
		horse[i].col = col;
		horse[i].dir = dir;
		horse[i].score -= map[nrow][ncol];
		horse[i].finish = finish;
	}
	return;
}
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 10; i++)
		cin >> b[i];

	init_map();

	for (int i = 0; i < 4; i++) {
		horse[i].row = 0;
		horse[i].col = 0;
		horse[i].score = 0;
		horse[i].dir = 0;
		horse[i].finish = false;
	}

	bfs(4, 0);

	cout << answer << "\n";

	return 0;
}