BOJ 17825 : 주사위 윷놀이

풀이 요약

구현

풀이 상세

1. 풀이 과정을 크게 나누자면 다음과 같다.
   • 게임판을 구현한다.
   • 말을 이동시킨다.
   • 이동시킨 곳에 다른 말이 있는지 확인한다.
   • 이동시킨 곳에 대한 점수를 저장한다.
   • 10번 다 플레이했다면 지금까지 더한 점수값을 최댓값과 비교한다.

2. 게임판은 중복되는 경우가 존재하여, idx 를 가지는 인접리스트와 점수를 가지는 배열을 따로 만들어 연결해주었다.
   

3. 먼저 4개의 말 중 현재 말을 옮기거나 현재 말을 옮기지 않고 다음 말을 옮기는 순으로 재귀를 구한다. 그 과정이 총 10번에 도달한 경우, 지금까지의 sum 값을 비교한다.

4. 말의 현재 좌표는 말 배열을 만들어 조건을 충족하는 경우 이동시킨 말의 좌표를 최신으로 업데이트 하였다.

5. 다른 말이 존재하는 지 확인하는 것은 그냥 현재 말이 가지고 있는 좌표를 일일히 반복문 돌리며, 그냥 비교했다.

6. 도착을 한 경우에는 점수가 없다! 나의 경우는 score[32] 에 그냥 어느값도 할당하지 않았다.

#include <iostream>
#include <vector>
using namespace std;
// dice, player, score
int d[10], p[4], s[33], ans;
vector<int> adj[33];

void input() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for (int i = 0; i < 10; i++) cin >> d[i];
}

int go(int idx, int cnt) {
    if (idx == 32) return 32;
    if (idx % 5 == 0 && idx > 0 && idx <= 15) {
        idx = adj[idx][1];
        cnt--;
    }
    if (!cnt) return idx;
    else {
        int curr = adj[idx][0];
        int next;
        while (--cnt) {
            if (curr == 32) break;
            next = adj[curr][0];
            curr = next;
        }
        return curr;
    }
}

bool check(int next, int idx) {
    if (next == 32) return false;
    for (int i = 0; i < 4; i++) {
        if (i == idx) continue;
        if (next == p[i]) return true;
    }
    return false;
}

void solve(int idx, int sum) {
    if (idx == 10) {
        ans = max(ans, sum);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int curr = p[i];
        int next = go(curr, d[idx]);
        if (check(next, i)) continue;
        p[i] = next;
        solve(idx + 1, sum + s[next]);
        p[i] = curr;
    }
}

void map() {
    // 출발 -> 40
    for (int i = 0; i < 20; i++) adj[i].push_back(i + 1);
    for (int i = 1; i <= 20; i++) s[i] = i * 2;
    // 10 -> 25
    adj[5].push_back(21); s[21] = 13;
    adj[21].push_back(22); s[22] = 16;
    adj[22].push_back(23); s[23] = 19;
    adj[23].push_back(24); s[24] = 25;
    // 20 -> 25
    adj[10].push_back(25);
    s[25] = 22; adj[25].push_back(26);
    s[26] = 24; adj[26].push_back(24);
    // 30 -> 25
    adj[15].push_back(27);
    s[27] = 28; adj[27].push_back(28);
    s[28] = 27; adj[28].push_back(29);
    s[29] = 26; adj[29].push_back(24);
    // 25 -> 40
    adj[24].push_back(30); s[30] = 30;
    adj[30].push_back(31); s[31] = 35;
    adj[31].push_back(20);
    // 도착
    adj[20].push_back(32);
}

void output() {
    cout << ans;
}

int main() {
    input();
    map();
    solve(0, 0);
    output();
}