BOJ 17825번: 주사위 윷놀이

문제

문제 바로가기> BOJ 17825번: 주사위 윷놀이

17825번: 주사위 윷놀이

 

풀이

각 칸에서 이동해야하는 다음칸, 점수를 저장해 두어야 하는데, 

이 때 약간의 노가다 작업?이 필요하다. 그 외에는 단순 백트래킹 문제이다 !

💡 문제 해결 Point

   처음에 파란지점 때문에 2차원 배열([이동칸][현위치] = 다음위치)을 만들어서
   바로 이동하게 하려고 했는데, 이렇게 하는 경우, 너무 많은 노가다 작업이 필요했다,,
   
   개인적으로, blueP 지점을 별도 배열로 가지고 있는 부분이 중요한 것 같다.
   이동 횟수가 최대 5번이므로, 시뮬레이션에 큰 부담이 되지 않고,
   체크해둔 블루 포인트를 이동 시작 시 확인해주면 쉽게 이동할 수 있다.
   (파란 칸에서 시작하는 경우에만, 파란색 화살표를 타고 이동하므로)

#include<iostream>
#define MAX 35
#define DEST 21
#define TURN 10
#define PIECE 4
using namespace std;

int ans=0;
int score[MAX];
int nextP[MAX], blueP[MAX];
int dice[TURN], piece[PIECE];

void init(){

    // 점수판
    for(int i=1; i<21; i++) score[i] = i*2;
    score[22]=13; score[23]=16; score[24]=19;
    score[25]=25; score[26]=30; score[27]=35;
    score[28]=28; score[29]=27; score[30]=26;
    score[31]=22; score[32]=24;

    // 다음 위치
    for(int i=0; i<21; i++) nextP[i]=i+1;
    for(int i=22; i<27; i++) nextP[i] = i+1;
    nextP[21]=21; 
    nextP[27]=20; nextP[28]=29; nextP[29]=30;
    nextP[30]=25; nextP[31]=32; nextP[32]=25;

    // 파란색 지점
    blueP[5]=22; blueP[10]=31; blueP[15]=28;
}

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

bool possible(int p, int cnt){
    if(blueP[p]) { p = blueP[p]; cnt--; }
    while(cnt--) p = nextP[p];
    for(int i=0; i<4; i++) {
        if(piece[i] == p && p!=DEST) return false; // 다른 말이 있는데, 도착칸이 아닌 경우
    } return true;
}

void solution(int cnt, int sum){ // 얻을 수 있는 점수의 최댓값
    if(cnt==TURN){
        ans = max(ans, sum);
        return;
    }
    for(int i=0; i<PIECE; i++){ // 말 4개 
        if(!possible(piece[i], dice[cnt])) continue; // 이동이 불가능한 경우

        int before = piece[i]; // copy
        int move_cnt = dice[cnt];

        // move
        if(blueP[piece[i]]) { piece[i] = blueP[piece[i]]; move_cnt--; }
        while(move_cnt--) piece[i] = nextP[piece[i]];
        solution(cnt+1, sum+score[piece[i]]);

        piece[i] = before; // recovery
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    input();
    solution(0, 0);
    cout << ans;
}