BOJ 17825 - 주사위 윷놀이(구현, 브루트포스, 백트래킹)

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

17825번: 주사위 윷놀이

- 주사위를 10번 던지면서 4개의 말 중 하나를 선택해서 움직인다. O(4^10) = 100만이므로 브루트포스 방식으로도 충분히 풀 수 있다

- 4^10 = 2^20 이므로 말을 선택하는 방식의 종류(seq) = 0~(1 << 20)-1 이 될 수 있다. 11(2) 값으로 비트연산해서 비트 2개씩 끊어서 읽으면서 말 00, 01, 10, 11에 대한 처리를 할 수 있다. seq 값대로 끝까지 말을 움직이면서 문제 조건대로 성립하지 않는 예외케이스를 모두 통과하면 ans와 비교해서 최대값을 구한다.

- 2차원 벡터를 통해서 윷판을 구현하였고, pos에 4개 말의 좌표를 저장한다. 0,1,2,3번째 루트의 값을 모두 넣어준다. 마지막 0은 도착지점.
v[0]에서 파란칸 index에 도달할 경우 v[1], v[2], v[3]으로 위치를 바꿔준다. 

- 말이 도착지점까지 간 것에 대한 예외처리, 말이 서로 겹치는 것에 대한 예외처리를 해줘야 한다. 이 부분이 생각보다 까다롭다

- 내가 구현한 방식으로는 v[1~3][c]가 25, 30, 35, 40일 경우에 다른 말과 겹치는 것에 대한 예외처리를 해줘야했다.
v[3] 첫번째 노드인 30과 v[1~3] 중간에 있는 노드 30에 대한 예외처리를 해주었다. 

#include <iostream>
#include <vector>
using namespace std;
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)
typedef pair<int, int> pii;

vector<vector<int>> v = {
    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0},
    {10, 13, 16, 19, 25, 30, 35, 40, 0},
    {20, 22, 24, 25, 30, 35, 40, 0},
    {30, 28, 27, 26, 25, 30, 35, 40, 0}};

int a[10], ans;

void go(int seq) {
    pii pos[4] = {{0, 0}, {0, 0}, {0, 0}, {0, 0}};
    bool isEnd[4] = {false};
    int score = 0;

    for (int i = 0; i < 10; ++i) {
        int n = seq & 3; // 00, 01, 10, 11
        seq /= 4;
        if (isEnd[n]) return;

        auto &[r, c] = pos[n];
        c += a[i];
        if (c >= v[r].size() - 1) {
            c = v[r].size() - 1;
            isEnd[n] = true;
        } else if (r == 0 && (c == 5 || c == 10 || c == 15)) {
            r = c / 5;
            c = 0;
        }
		
        for (int m = 0; m < 4; ++m) {
            if (isEnd[n]) break;
            if (n == m) continue;
            if (pos[n] == pos[m]) return;

            const auto &[r1, c1] = pos[m];
            if (v[r][c] == 25 || v[r][c] == 35 || v[r][c] == 40) {
                if (v[r][c] == v[r1][c1]) return;
            }
            if (v[r][c] == 30 && v[r1][c1] == 30) {
                if (r == 3 || r1 == 3) continue;
                return;
            }
        }
        score += v[r][c];
    }
    ans = max(ans, score);
}

int main() {
    FASTIO;
    for (int i = 0; i < 10; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < (1 << 20); ++i) { // 4^10
        go(i);
    }
    cout << ans;
    return 0;
}