[백준/BOJ] 17825번 주사위 윷놀이

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

17825번: 주사위 윷놀이

빡센 완탐문제(짱 어렵당), 완벽히 풀 수 있을 때까지 반복해볼 것

 

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

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int t, n, m, k, sx, sy, ex, ey, x, y, answer, root;
// a : 주사위 입력값, mal : 말의 위치 저장(변환된 위치), v : 트리의 노드 위치를 변환하여 저장
int a[11], mal[4], v[101];
vector<int> adj[101];

// 주사위 입력값만큼 말 이동하기
int BFS(int here, int cnt) {
	if(here == 100) return 100;
	if(adj[here].size() > 1) {
		here = adj[here][1];
		cnt--;
	}
	if(cnt > 0) {
		queue<int> q;
		q.push(here);
		int there;
		while(!q.empty()) {
			int x = q.front();
			q.pop();
			there = adj[x][0];
			q.push(there);
			if(there == 100) break;
			cnt--;
			if(cnt == 0) break;
		}
		return there;
	}
	
	return here;
}

// 특정 위치에 말이 있는지 확인
bool isMal(int mal_idx, int idx) {
	if(mal_idx == 100) return false;
	for(int i = 0; i < 4; i++) {
		if(i == idx) continue;
		if(mal[i] == mal_idx) return true;
	}
	return false;
}

// 주사위 이동에 따라 생성되는 점수의 모든 경우를 구하기
int DFS(int here) {
	if(here == 10) return 0;
	int res = 0;
	for(int i = 0; i < 4; i++) {
		int temp_idx = mal[i];
		int mal_idx = BFS(temp_idx, a[here]);
		if(isMal(mal_idx, i)) continue;
		mal[i] = mal_idx;
		res = max(res, DFS(here + 1) + v[mal_idx]);
		mal[i] = temp_idx;
	}
	return res;
}

// 인접리스트로 트리 생성
void init() {
	v[1] = 2, v[2] = 4, v[3] = 6, v[4] = 8, v[5] = 10;
	v[6] = 12, v[7] = 14, v[8] = 16, v[9] = 18, v[10] = 20;
	v[11] = 22, v[12] = 24, v[13] = 26, v[14] = 28, v[15] = 30;
	v[16] = 32, v[17] = 34, v[18] = 36, v[19] = 38, v[20] = 40;
	v[21] = 13, v[22] = 16, v[23] = 19, v[24] = 22, v[25] = 24;
	v[26] = 28, v[27] = 27, v[28] = 26, v[29] = 25, v[30] = 30, v[31] = 35;
	
	// 2 ~ 40
	for(int i = 0; i < 20; i++) {
		adj[i].push_back(i + 1);
	} 
	
	// 10 ~ 25
	adj[5].push_back(21);
	adj[21].push_back(22);
	adj[22].push_back(23);
	adj[23].push_back(29);
	
	// 20 ~ 25
	adj[10].push_back(24);
	adj[24].push_back(25);
	adj[25].push_back(29);
	
	// 30 ~ 25
	adj[15].push_back(26);
	adj[26].push_back(27);
	adj[27].push_back(28);
	adj[28].push_back(29);
	
	// 25 ~ 40
	adj[29].push_back(30);
	adj[30].push_back(31);
	adj[31].push_back(20);
	adj[20].push_back(100);
}


int main() {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	init();
	for(int i = 0; i < 10; i++) {
		cin >> a[i];
	}
	
	cout << DFS(0);
}