[백준] 17825 주사위 윷놀이 (C++)

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

17825번: 주사위 윷놀이

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

 

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

---

풀이

굉장히 까다롭고 생각할 것이 많은 문제이다.

얻을 수 있는 점수의 최댓값을 출력해야 하기 때문에 그리디적으로 접근하려 했으나

도저히 적절할 방법이 떠오르지 않고 백트래킹으로 모든 경우의 수를 조사하기로 하였다.

 

다음은 유의해야 할 부분이다.

• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.

처음에는 1번 말이 칸 A로 이동을 마치고 해당 칸 A에 다른 2번 말이 있는 경우 다음 차례에 2번 말이 이동하지 못한다고 이해하였다. 그러나 이가 아니라 애초에 1번 말이 칸 A로 이동하지 못하는 것이었다.

즉, 1번 말이 칸 A로 이동하려 하는데 해당 칸 A에 2번 말이 있는 경우 1번 말은 칸 A로 이동하지 못하는 것이다.

 

또한 10, 20, 30번 칸에 있는 말은 파란색 화살표를 따라 다른 경로로 이동하는데 이를 처리하는 부분이 굉장히 까다롭다.

단순히 10번 칸에서 5만큼 이동하여 30에 도착했다고 이를 저장한다면 다음 번에 움직일 때 35로 갈 지 28로 갈 지를 모르기 때문이다.

 

이에 따라 중앙에 있는 칸들은 음수로 처리하여 각 칸들을 구분하였다.

단, 여기서 또다시 주의할 점은 칸 '40'을 처리하는 부분이다.

35에서 40으로 갈 수 도 있고, 38에서도 40으로 갈 수 있는데 40은 같은 칸이므로

-40과 40으로 구분하여 저장하면 안되고 40으로 저장해야 한다.

 

코드

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

int marker[4] = {0, 0, 0, 0};
int dices[10];
int answer = 0;

int moveSpecial(int curDice, int targetMarker){
    while (curDice-- && targetMarker >= -40){
        if (targetMarker == -13 || targetMarker == -16){
            targetMarker -= 3;
        }
        else if (targetMarker == -22){
            targetMarker -= 2;
        }
        else if (targetMarker == -28 || targetMarker == -27 || targetMarker == -26){
            targetMarker++;
        }
        else if (-40 <= targetMarker && targetMarker <= -25){
            targetMarker -= 5;
        }
        else if (targetMarker == -19 || targetMarker == -24){
            targetMarker = -25;
        }
    }
    return targetMarker;
}

// 윷놀이판 외곽을 제외한 중심부에 있는 말은 음수로 처리
void tracking(int dice, int score){
    // 주사위를 전부 굴렸다면
    if (dice >= 10){
        answer = max(answer, score);
        return;
    }
    for (int i = 0; i < 4; i++){
        int curDice = dices[dice];
        int targetMarker = marker[i];
        int addScore = 0;
        // 도착점에 있는 경우
        if (targetMarker > 40){
            continue;
        }
        // 10인 경우
        else if (targetMarker == 10){
            curDice--;
            targetMarker = -13;
            targetMarker = moveSpecial(curDice, targetMarker);
            addScore = -targetMarker;
        }
        // 20인 경우
        else if (targetMarker == 20){
            curDice--;
            targetMarker = -22;
            targetMarker = moveSpecial(curDice, targetMarker);
            addScore = -targetMarker;
        }
        // 30인 경우
        else if (targetMarker == 30){
            curDice--;
            targetMarker = -28;
            targetMarker = moveSpecial(curDice, targetMarker);
            addScore = -targetMarker;
        }
        // 음수인 경우(윷놀이판 중앙에 위치한 경우)
        else if (targetMarker < 0){
            targetMarker = moveSpecial(curDice, targetMarker);
            // 만약 -40을 넘었다면
            if (targetMarker == -45){
                addScore = 0;
                targetMarker = 45;
            }
            // 도착하지 못했다면
            else{
                addScore = -targetMarker;
                if (targetMarker == -40){
                    targetMarker = 40;
                }
            }
        }
        // 그 이외의 경우
        else{
            targetMarker += (curDice * 2);
            // 만약 40을 넘어 도착했다면
            if (targetMarker > 40){
                addScore = 0;
            }
            // 도착하지 못했다면
            else{
                addScore = targetMarker;
            }
        }
        // 만약 이동하려는 칸에 다른 말이 있었다면
        bool isDuplicate = false;
        for (int j = 0; j < 4; j++){
            if (marker[j] == targetMarker && targetMarker <= 40){
                isDuplicate = true;
                break;
            }
        }
        if (isDuplicate){
            continue;
        }
        // 백트래킹
        int tmp = marker[i];
        marker[i] = targetMarker;
        tracking(dice+1, score+addScore);
        marker[i] = tmp;
    }
}

int main(){
    for (int i = 0; i < 10; i++){
        cin >> dices[i];
    }

    tracking(0, 0);
    cout << answer;
}