[Baekjoon][17825] 주사위 윷놀이

출처 - 백준사이트

17825. 주사위 윷놀이

나의 풀이

주사위 윷판을 어떤 알고리즘으로 할지 고민을 많이 고민을 한 문제.
나는 윷판을 리스트 형태로 구현하였다. 구현하기 위해 Node에 대한 구조체를 만들었다.
시작점은 score = 0, 도착점은 score = -1로 설정하였다.

#include <iostream>
#include <cstring>
#include <vector>
#include <tuple>

using namespace std;

typedef struct _node {
    _node(int score = 0) : score(score) { ori_next = nullptr, other_next = nullptr; }

    struct _node& operator=(struct _node& ref) {
        if (&ref != nullptr) {
            this->score = ref.score;
            this->ori_next = ref.ori_next;
            this->other_next = ref.other_next;
        }

        return *this;
    }

    struct _node* Next() {
        return this->ori_next;
    }

    struct _node* TurnNext() {
        return this->other_next;
    }

    int score;
    struct _node* ori_next;
    struct _node* other_next;
} Node;

int dice[10];
int result;
Node map;
Node horse[4];

bool moving(int idx, int num) {
    Node *check = &horse[idx];
    int i = 0;

    if (check->score == 10 || check->score == 20 || check->score == 30) { // 파란색으로 이동해야하는 경우
        if (check->other_next != nullptr) {
            check = check->TurnNext();

            i = 1;
        }
    }

    for ( ; i < num ; i++) {
        check = check->Next();

        if (check->score == -1) { // 도착점에 도달한 경우
            horse[idx] = *check;
            return true;
        }
    }

    for (int i = 0 ; i < 4 ; i++) {
        if (idx == i)
            continue;

        if (check->score == horse[i].score) { // 이동했는데 같은 노드에 있는지 판단
            if ((check->ori_next == horse[i].ori_next) && (check->other_next == horse[i].other_next))
                return false;
        }
    }

    horse[idx] = *check;
    return true;
}

void pick(int num, int sum) {
    if (num == 10) {
        if (result < sum)
            result = sum;

        return;
    }

    for (int i = 0 ; i < 4 ; i++) {
        if (horse[i].score != -1) {
            Node temp[4];

            memcpy(temp, horse, sizeof(temp));

            if (moving(i, dice[num])) {
                if (horse[i].score != -1)
                    pick(num + 1, sum + horse[i].score);
                else
                    pick(num + 1, sum);
            }

            memcpy(horse, temp, sizeof(horse));
        }
    }
}

void makeMap() {
    Node* prv_node = &map;
    Node* score_10 = nullptr;
    Node* score_20 = nullptr;
    Node* score_30 = nullptr;
    Node* score_40 = nullptr;

    for (int i = 1 ; i <= 20 ; i++) {
        Node* new_node = new Node(i*2);
        prv_node->ori_next = new_node;
        prv_node = new_node;

        if (i*2 == 10)
            score_10 = new_node;
        else if (i*2 == 20)
            score_20 = new_node;
        else if (i*2 == 30)
            score_30 = new_node;
        else if (i*2 == 40) {
            score_40 = new_node;
            score_40->ori_next = new Node(-1);
        }
    }

    Node *score_25 = new Node(25);
    score_25->ori_next = new Node(30);
    score_25->ori_next->ori_next = new Node(35);
    score_25->ori_next->ori_next->ori_next = score_40;

    score_10->other_next = new Node(13);
    score_10->other_next->ori_next = new Node(16);
    score_10->other_next->ori_next->ori_next = new Node(19);
    score_10->other_next->ori_next->ori_next->ori_next = score_25;

    score_20->other_next = new Node(22);
    score_20->other_next->ori_next = new Node(24);
    score_20->other_next->ori_next->ori_next = score_25;

    score_30->other_next = new Node(28);
    score_30->other_next->ori_next = new Node(27);
    score_30->other_next->ori_next->ori_next = new Node(26);
    score_30->other_next->ori_next->ori_next->ori_next = score_25;

    horse[0] = map;
    horse[1] = map;
    horse[2] = map;
    horse[3] = map;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    for (int idx = 0 ; idx < 10 ; idx++)
        cin >> dice[idx];

    makeMap();
    pick(0, 0);

    cout << result;

    return 0;
}