백준 17825 주사위 윷놀이 풀이(c++)

문제

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

 

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

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

입력

 

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

출력

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

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int Jusawi[14], Mal[4], N = 10;
int v[104];
vector<int> vAdj[54];

int Move(int iHere, int iCount)
{
    if (iHere == 100)
        return 100;  

    if (vAdj[iHere].size() >= 2) 
    {
        iHere = vAdj[iHere][1];
        iCount--; 
    }

    while (iCount--)
    {
        iHere = vAdj[iHere][0];
        if (iHere == 100)
            break;  
    }

    return iHere;
}

bool isMal(int iMalIndex, int iIndex)
{
    if (iMalIndex == 100)
        return false;

    for (int i = 0; i < 4; i++) 
    {
        if (i == iIndex)
            continue;
        if (Mal[i] == iMalIndex)
            return true;
    }
    return false;
}

void add(int iHere, int iThere)
{
    vAdj[iHere].push_back(iThere);
}

void setMap()
{
    for (int i = 0; i <= 19; i++)
        add(i, i + 1);

    add(5, 21); add(21, 22); add(22, 23); add(23, 24);
    add(15, 29); add(29, 30); add(30, 31); add(31, 24);
    add(10, 27); add(27, 28); add(28, 24); add(24, 25);
    add(25, 26); add(26, 20); add(20, 100);

    v[1] = 2; v[2] = 4; v[3] = 6; v[4] = 8; v[5] = 10;
    v[6] = 12; v[7] = 14; v[8] = 16; v[9] = 18; v[10] = 20;
    v[11] = 22; v[12] = 24; v[13] = 26; v[14] = 28; v[15] = 30;
    v[16] = 32; v[17] = 34; v[18] = 36; v[19] = 38; v[20] = 40;
    v[21] = 13; v[22] = 16; v[23] = 19; v[24] = 25;
    v[27] = 22; v[28] = 24; v[25] = 30; v[26] = 35;
    v[29] = 28; v[30] = 27; v[31] = 26;
}

int go(int iHere)
{
    if (iHere == N)
        return 0;

    int iResult = 0;
    for (int i = 0; i < 4; i++) 
    {
        int iTemp_idx = Mal[i];
        int iMal_idx = Move(iTemp_idx, Jusawi[iHere]);

        if (isMal(iMal_idx, i))
            continue;  

        Mal[i] = iMal_idx;
        iResult = max(iResult, go(iHere + 1) + v[iMal_idx]);
        Mal[i] = iTemp_idx; 
    }
    return iResult;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    for (int i = 0; i < N; i++)
        cin >> Jusawi[i];

    setMap();
    cout << go(0) << "\n"; 

    return 0;
}

 

BFS 와 백트래킹을 이용해서 풀이.

맵을 만드는 부분이 까다로웠는데  두갈래로 나눠질 경우하나 더 넣어서 요소가 2개일 경우를 한번더 판별해 해결하였다.