(C++) - 백준(BOJ) 17825번 : 주사위 윷놀이

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

brute force로 푼 문제였습니다.

 

풀이방법

 1. 먼저 윷판을 만듭니다.

 

 각 위치를 파란색 글씨로 넣어 보았습니다. 해당 위치에는 6개의 정보가 들어있는 2차원 배열로 표현합니다.

정보는

 배열의 한 인덱스(위치) => {해당 위치의 점수, 주사위 1이 나왔을 때 다음위치, 2가 나왔을때, 3... , 4... , 5... }가 됩니다.

 

2. 4개의 말의 위치정보를 비트로 표현합니다.

 한 턴당 비트 2개로 4개의 말 중 어떤 말이 움직였는지를 나타낼 수 있습니다. 움직이는 말을 0으로 표현했습니다. 4턴에 대한 각 말들의 움직임을 표로 예를 들면

	1번 말	2번 말	3번 말	4번 말	표현비트
1 turn	0	-	-	-	00
2 turn	-	0	-	-	01
3 turn	-	-	0	-	10
4 turn	-	-	-	0	11

이렇게 표현될 수 있습니다.

 

3. 점수를 계산합니다.

 모든 말의 움직임 상태에 대해 10개의 주사위로 다음 위치를 파악할 수 있습니다. 이를 통해 점수를 계산해서 최대값을 출력하면 됩니다. 이 때 각 말의 위치정보를 저장할 배열과 해당 위치를 이미 말이 점유하고 있는지 여부를 판별할 visited 배열이 필요합니다. 한 턴당 어떤 말이 움직이는지의 정보는 state >> (한 턴 * 2) & 0x03을 계산한다면 구할 수 있습니다. *2의 이유는 한 턴당 2개의 비트를 사용하기 때문이고 & 0x03은 state의 마지막 2비트를 구하기 위함 입니다.

 

 말이 지나갈 수 없는 경우도 생각해야 합니다. 만약 이미 어떤 말이 한 턴당 이동할 다음 위치에 있고 또한 도착칸이 아니라면 갈 수 없기 때문에 작은 값 -1을 반환함으로써 이상한 점수값이 나옴을 방지합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
// {점수, 각 주사위 1나왔을 때 위치,2,3,4,5}
const int table[33][6]={
    //0 ~ 4
    {0 , 1 , 2 , 3 , 4 , 5 },
    {2 , 2 , 3 , 4 , 5 , 6 },
    {4 , 3 , 4 , 5 , 6 , 7 },
    {6 , 4 , 5 , 6 , 7 , 8 },
    {8 , 5 , 6 , 7 , 8 , 9 },

    //5 ~ 9
    {10, 23, 24, 25, 28, 29},
    {12, 7 , 8 , 9 , 10, 11},
    {14, 8 , 9 , 10, 11, 12},
    {16, 9 , 10, 11, 12, 13},
    {18, 10, 11, 12, 13, 14},

    //10 ~ 14
    {20, 26, 27, 28, 29, 30},
    {22, 12, 13, 14, 15, 16},
    {24, 13, 14, 15, 16, 17},
    {26, 14, 15, 16, 17, 18},
    {28, 15, 16, 17, 18, 19},

    //15 ~ 19
    {30, 20, 21, 22, 28, 29},
    {32, 17, 18, 19, 31, 32},
    {34, 18, 19, 31, 32, 32},
    {36, 19, 31, 32, 32, 32},
    {38, 31, 32, 32, 32, 32},

    //20 ~ 24
    {28, 21, 22, 28, 29, 30},
    {27, 22, 28, 29, 30, 31},
    {26, 28, 29, 30, 31, 32},
    {13, 24, 25, 28, 29, 30},
    {16, 25, 28, 29, 30, 31},

    //25 ~ 29
    {19, 28, 29, 30, 31, 32},
    {22, 27, 28, 29, 30, 31},
    {24, 28, 29, 30, 31, 32},
    {25, 29, 30, 31, 32, 32},
    {30, 30, 31, 32, 32, 32},

    //30 ~ 32
    {35, 31, 32, 32, 32, 32},
    {40, 32, 32, 32, 32, 32},
    {0 , 32, 32, 32, 32, 32},
};

int dice[10], ans;

int getScore(int state){
    int ret = 0;
    bool visited[33] = {false, };
    int pos[4] = {0 ,}; //각 말의 위치 저장
    for(int turn = 0; turn < 10; turn++){
        int move = dice[turn];
        int horse = (state >> (turn * 2)) & 0x03; //state마지막 2bit이 대입됨
        int &curPos = pos[horse];
        int nextPos = table[curPos][move];
        int score = table[nextPos][0];
        if(visited[nextPos] && nextPos != 32) return -1;
        ret += score;
        visited[curPos] = false;
        visited[nextPos] = true;
        curPos = nextPos;
    }
    return ret;
}
int main(){
    for(int i = 0; i < 10; i++) cin >> dice[i];

    for(int state = 0; state < 1<<20; state++){
        int score = getScore(state);
        ans = max(ans,score);
    } 
    cout << ans <<'\n';
}