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

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

 

구현 문제입니다. 그래프를 만든 다음에 말이 이동할 수 있는 모든 경우의 수를 만들어 각 경우의 수마다 점수를 구해 최댓값을 구하면 됩니다.

10번의 턴에서 각 턴마다 몇번 말을 움직일지 모든 경우의 수를 만드는 것은 브루트포스로 만들면 됩니다.

 

\(4^{10}\)가지의 경우의 수가 생기는데 이 정도면 충분히 시간 안에 돌아가고요, 그리고 중간에 말이 겹치는 경우나 이미 도착한 말을 선택하는 경우를 pruning 하면 경우의 수가 더 줄어들기 때문에 시간제한은 넉넉합니다.

 

그림 만들기도 힘드네요

그래프를 만드는게 좀 귀찮은데요, 저는 위 그림처럼 만들었습니다. 인덱스를 저렇게 만든 이유는 최대한 반복문을 써서 타이핑을 줄여보려고 대충 저렇게 했습니다. 굳이 따라할 필요는 없고요 그냥 적당~히 그래프로 만들면 됩니다.

파란색 노드를 제외한 노드는 전부 간선이 하나뿐이고, 파란색 노드는 [0]이 빨간색 간선, [1]이 파란색 간선이 되도록 구성했습니다.

노드에 써있는 점수를 이용하면 그래프를 직접 만들지 않아도 되지 않을 것 같다고 생각했는데요, 점수가 같은 노드가 있어서 그냥 그래프로 만들었습니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

const int START_NODE = 0;
const int END_NODE = 32;
const int SCORES[33] = { 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,13,16,19,25,22,24,28,27,26,30,35,0 };

vector<int> graph[33];
vector<int> dice;


// 출발 노드와 몇 칸 이동할지 입력받음
// score 변수로는 이동할 때 추가되는 점수를 누적
// 목적지 노드를 반환
int next(int start, int cnt, int& score) {
	int dest = start;

	// 파란색
	if (start == 5 || start == 10 || start == 15) {
		dest = graph[start][1];
		--cnt;
	}

	while (cnt--) {
		dest = graph[dest][0];
		
		if (dest == END_NODE) break;
	}

	score = SCORES[dest];
	return dest;
}

void init() {
	// 그래프 생성
	for (int i = 0; i <= 19; ++i) {
		graph[i].push_back(i + 1);
	}
	graph[20].push_back(32);

	graph[5].push_back(21);
	for (int i = 21; i <= 23; ++i) {
		graph[i].push_back(i + 1);
	}

	graph[10].push_back(25);
	graph[25].push_back(26);
	graph[26].push_back(24);
	
	graph[15].push_back(27);
	graph[27].push_back(28);
	graph[28].push_back(29);
	graph[29].push_back(24);

	graph[24].push_back(30);
	graph[30].push_back(31);
	graph[31].push_back(20);
}

int bruteforce(vector<int>& toMove, int toPick) {
	if (toPick == 0) {
		int score = 0;
		int pos[4] = {0};
		
		// 이미 도착한 말을 고르거나
		// 중간에 말 겹치면 바로 끝냄
		for (int i = 0; i < 10; ++i) {
			auto& idx = toMove[i];
			if (pos[idx] == END_NODE)
				return 0;

			int _s = 0;
			int dst = next(pos[idx], dice[i], _s);

			if (dst != END_NODE && find(begin(pos), end(pos), dst) != end(pos))
				return 0;

			pos[idx] = dst;
			score += _s;
		}

		return score;
	}


	//pick
	int ret = 0;
	for (int i = 0; i < 4; ++i) {
		toMove.push_back(i);
		ret = max(ret, bruteforce(toMove, toPick - 1));
		toMove.pop_back();
	}
	return ret;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	init();

	dice.resize(10);
	for (auto& c : dice)
		cin >> c;

	vector<int> to_move;
	to_move.reserve(10);
	cout << bruteforce(to_move, 10) << '\n';


	return 0;
}

코드 돌려보고 '이거 너무 느린데? 시간초과 나는거 아니야?' 라고 생각하실 수 있겠지만 릴리즈로 돌리면 빠릅니다. 걱정 안해도 됩니다.