[BOJ] 17825 - 주사위 윷놀이

[백준] 17825 - 주사위 윷놀이

구현에서 가장 편한 방법을 찾아가고 있다. 이번에는 무식하게 각 위치에서 주사위마다 갈 지점을 일일이 vector로 저장해놓고 시작했다. if else로 일일이 지정하는거랑 비슷한 것 같기도 하고.. 코딩하면서 헷갈리지 않도록 하는 것이 가장 중요한 것 같다. 늘 그렇듯 구현만 하면 되기 때문에 시간복잡도는 크게 중요하지 않아 편한 문제다.

소스코드

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

int point[35], ans, piece[4], dice[10];
bool ck[35];
map<int, vector<int>> to_go;

void init() {
    for (int i = 1; i <= 20; i++) {
        point[i] = i * 2;
        for (int j = 1; j <= 5; j++) {
            if (i + j <= 20) to_go[i].push_back(i + j);
            else to_go[i].push_back(-1);
        }
    }
    point[21] = 13; point[22] = 16; point[23] = 19;
    point[24] = 28; point[25] = 27; point[26] = 26;
    point[27] = 22; point[28] = 24; point[29] = 25;
    point[30] = 30; point[31] = 35;
    to_go[5] = { 21, 22, 23, 29, 30 };
    to_go[10] = { 27, 28, 29 ,30, 31 };
    to_go[15] = { 24, 25, 26, 29, 30 };
    to_go[20] = { -1, -1, -1, -1, -1 };
    to_go[21] = { 22, 23, 29, 30, 31 };
    to_go[22] = { 23, 29, 30, 31, 20 };
    to_go[23] = { 29, 30, 31, 20, -1 };
    to_go[24] = { 25, 26, 29, 30, 31 };
    to_go[25] = { 26, 29, 30, 31, 20 };
    to_go[26] = { 29, 30, 31, 20, -1 };
    to_go[27] = { 28, 29, 30, 31, 20 };
    to_go[28] = { 29, 30, 31, 20, -1 };
    to_go[29] = { 30, 31, 20, -1, -1 };
    to_go[30] = { 31, 20, -1, -1, -1 };
    to_go[31] = { 20, -1, -1, -1, -1 };
}

void go(int idx, int cnt) {
    if (idx >= 10) {
        ans = max(cnt, ans);
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (piece[i] == -1) continue;
        if (piece[i] == 0) {
            if (ck[dice[idx]]) continue;
            piece[i] = dice[idx];
            ck[dice[idx]] = true;
            go(idx + 1, cnt + point[dice[idx]]);
            piece[i] = 0;
            ck[dice[idx]] = false;
        }
        else if (to_go[piece[i]][dice[idx] - 1] == -1) {
            int tmp = piece[i];
            ck[piece[i]] = false;
            piece[i] = -1;
            go(idx + 1, cnt);
            piece[i] = tmp;
            ck[piece[i]] = true;
        }
        else if (!ck[to_go[piece[i]][dice[idx] - 1]]) {
            if (ck[to_go[piece[i]][dice[idx] - 1]]) continue;
            int tmp = piece[i];
            ck[piece[i]] = false;
            piece[i] = to_go[piece[i]][dice[idx] - 1];
            ck[piece[i]] = true;
            go(idx + 1, cnt + point[piece[i]]);
            ck[piece[i]] = false;
            piece[i] = tmp;
            ck[piece[i]] = true;
        }
    }
}

int main(void) {
    init();
    for (int i = 0; i < 10; i++)
        scanf("%d", dice + i);
    go(0, 0);
    printf("%d", ans);
    return 0;
}