문제

문제 링크

해설

• 어쩌면 가장 당황스러운 종류의 시뮬레이션 문제인 것 같습니다. 가장 구현에 가까운 문제일 수도 있곘네요.
• 문제에 주어진 윷놀이 도형을 어떻게 하면 구현할 수 있을까요? 10, 20, 30이 적힌 노드에서 두갈래로 나뉘고, 해당 점에 멈췄을 때는 무조건 파란 화살표를 따라가야 한다는 점을 어떻게 편하게 구현할 수 있을까요?
• 저마다 여러 구현방법이 있겠지만, 방향성이 있는 노드를 서로 연결하기에는std::list<> 또는 std::vector<>가 좋은 방법일 것 같습니다.
  
• 게임판 인덱스 순서는 여러분이 마음대로 지정하면 됩니다. (이 문제의 가장 중요하면서도, 알고리즘 면에서는 중요하지 않은 부분이라...)

int solve(int depth) {
	if (depth == LIMIT) return 0;
	
	int ret = 0;
	for (int& horse: horses) {
		int tempIdx = horse;
		int nextIdx = moveHorse(horse, dice[depth]);
		
		// Can't move if there is already a horse.
		if (isThereHorse(nextIdx)) continue;
		
		horse = nextIdx;		// Set
		ret = max(ret, solve(depth + 1) + score[nextIdx]);
		horse = tempIdx;		// Reset
	}
	return ret;
}

• 모든 경우의 수 탐색은 기본적으로 재귀를 사용해서 구현했습니다.
• 각 말이 depth번째 주사위에 적힌 눈에 따라 이동합니다.
• 이때 이동할 지점을 계산하는 moveHorse()함수에서는
  • 만일 현재 지점이 10, 20, 30이 적힌 노드라면 갈 수 있는 길이 2개이므로
  • adj[here].size() >= 2 일 것입니다. 이럴 때는 무조건 파란 화살표를 따라가야 하므로 현재 지점을 adj[here][1]로 한 칸 이동합니다. (10 노드라면 13, 20 노드라면 22로 이동한 상황입니다.)
• 만일 이동할 지점에 이미 말이 있다면, 이동하지 않습니다.

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int LIMIT = 10, START = 0, FINISH = 32;

array<int, 4> horses;
array<int, LIMIT> dice;
array<int, FINISH + 1> score;
vector<int> adj[FINISH + 1];

void initializeMap() {
	// 0. Start
	adj[START].push_back(1);
	// 1. Red arrow
	for (int i = 1; i < 20; ++i) adj[i].push_back(i + 1);
	// 2. Blue arrow
	adj[5].push_back(21); adj[21].push_back(22); adj[22].push_back(23); adj[23].push_back(24);
	adj[15].push_back(29); adj[29].push_back(30); adj[30].push_back(31); adj[31].push_back(24);
	adj[10].push_back(27); adj[27].push_back(28); adj[28].push_back(24);
	adj[24].push_back(25); adj[25].push_back(26); adj[26].push_back(20);
	// 3. Finish
	adj[20].push_back(FINISH);
	// 4. Give score to each panels
	for (int i = 1; i <= 20; ++i) score[i] = 2 * i;
	score[21] = 13; score[22] = 16; score[23] = 19; score[24] = 25;
	score[25] = 30; score[26] = 35; score[27] = 22; score[28] = 24;
	score[29] = 28; score[30] = 27; score[31] = 26;
}

int moveHorse(int here, int len) {
	if (here == FINISH) return FINISH;
	// If 'here' is blue arrow position, then follow blue arrow.
	if (adj[here].size() >= 2) {
		here = adj[here][1];
		len--;
		if (len == 0) return here;
	}
	queue<int> q;
	q.push(here);
	while (!q.empty()) {
		int here = q.front();
		q.pop();
		
		int there = adj[here][0];
		q.push(there);
        len--;
        
		if (there == FINISH || len == 0) return there;
	}
}

bool isThereHorse(int there) {
	if (there == FINISH) return false;
	for (const int& horse : horses)
		if (horse == there) return true;
	return false;
}

int solve(int depth) {
	if (depth == LIMIT) return 0;
	
	int ret = 0;
	for (int& horse: horses) {
		int tempIdx = horse;
		int nextIdx = moveHorse(horse, dice[depth]);
		
		// Can't move if there is already a horse.
		if (isThereHorse(nextIdx)) continue;
		
		horse = nextIdx;		// Set
		ret = max(ret, solve(depth + 1) + score[nextIdx]);
		horse = tempIdx;		// Reset
	}
	return ret;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
    initializeMap();
	for (int i = 0; i < LIMIT; ++i) cin >> dice[i];
	cout << solve(0);
}

소스코드 링크

결과