백준 17825번 : 주사위 윷놀이 - 백트래킹

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

17825번: 주사위 윷놀이

#include <bits/stdc++.h>

using namespace std;

int dice[11];

int nextPosition[33] ={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,32,22,23,29,25,29,27,28,29,30,31,20,32};
int point[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,22,24,28,27,26,25,30,35,0};


int horsePosition[4];
int ans = 0;


int horseMove(int x, int cnt){
    //already arrive
    if(x==32) return -1;

    //nx : other horse

    //blue move
    if(x==5){
        x = 21;
        cnt--;
    }
    else if(x==10){
        x = 24;
        cnt--;
    }
    else if(x==15){
        x = 26;
        cnt--;
    }
    //이동
    for(int i=0; i<cnt; i++){
        x = nextPosition[x];
    }

    //other horse
    for(int i=0; i<4; i++){
        if(x!=32 && horsePosition[i] == x){
            return -1;
        }
    }

    return x;
}


void backTrack(int L, int curPoint) {
    if (L == 10) {
        ans = max(ans, curPoint);
        return;
    }

    for (int i = 0; i < 4; i++) {
        int x = horsePosition[i];
        int nx = horseMove(horsePosition[i], dice[L]);
        if (nx < 0) continue;
        horsePosition[i] = nx;
        backTrack(L + 1, point[nx] + curPoint);
        horsePosition[i] = x;
    }
}



int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    backTrack(0, 0);

    cout << ans << '\n';
}