Baekjoon 17825번 주사위 윷놀이

문제

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

걸린 시간

04 : 07 : 56

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int dice[10];
vector<pair<int, int>> adj[33]; // current point, next index

void makeBoard(){
    // start to 40
    for(int i = 0; i <= 20; i++)
        adj[i].push_back(make_pair(2*i, i+1));
    // blue
    adj[5].push_back(make_pair(10, 22));
    adj[10].push_back(make_pair(20, 25));
    adj[15].push_back(make_pair(30, 27));
    // end
    adj[21].push_back(make_pair(0, 0));
    // 10 to 25
    adj[22].push_back(make_pair(13, 23));
    adj[23].push_back(make_pair(16, 24));
    adj[24].push_back(make_pair(19, 30));
    // 20 to 25
    adj[25].push_back(make_pair(22, 26));
    adj[26].push_back(make_pair(24, 30));
    // 30 to 25
    adj[27].push_back(make_pair(28, 28));
    adj[28].push_back(make_pair(27, 29));
    adj[29].push_back(make_pair(26, 30));
    // 25
    adj[30].push_back(make_pair(25, 31));
    // 25 to 40
    adj[31].push_back(make_pair(30, 32));
    adj[32].push_back(make_pair(35, 20));
}

int solve(int turn, int point, vector<int> piece){
    // 기저 사례
    if(turn == 10) return point;
    // 재귀 호출
    int ret = -INF;
    for(int i = 0; i < 4; i++){
        auto p = piece;
        int cur = p[i];
        if(cur == 21) continue;
        if(cur == 5 || cur == 10 || cur == 15)
            cur = adj[cur][1].second;
        else
            cur = adj[cur][0].second;
        for(int j = 1; j < dice[turn]; j++){
            if(cur == 21) break;
            cur = adj[cur][0].second;
        }
        bool isValid = true;
        for(int j = 0; j < 4; j++)
            if(cur != 21)
                if(piece[j] == cur) isValid = false;
        if(isValid){
            p[i] = cur;
            ret = max(ret, solve(turn+1, point+adj[cur][0].first, p));
        }
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for(auto& i : dice) cin >> i;
    makeBoard();
    vector<int> piece(4, 0);
    cout << solve(0, 0, piece);
    return 0;
}

윷놀이 판을 링크드 리스트로 구현했으면 시간이 이렇게 오래 걸리진 않았을 것 같다.

말의 개수가 4개 뿐이라 위치를 관리하는 배열을 레퍼런스 변수로 사용하지 않았다. (backtracking -> brute force)