[백준 c++] 17825 주사위 윷놀이

문제

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

4개의 말을 1~5까지 적힌 5면체 주사위를 10번 굴려서 이동시킨다.
파란 화살표가 적힌 칸에서 시작하면 파란 화살표 방향대로 움직여야한다.
a말의 이동이 마치는 칸에 b말이 있으면 a말은 그 칸으로 이동하지 못한다.
(단, 그 칸이 도착 칸이면 상관 없다.) 말의 이동을 마칠 때 해당 칸의 번호가 점수에 더해진다.
점수의 최대값을 구하는 문제다.

풀이

맵

맵 규칙을 찾아보려고 했는데 벡터에 값을 다 넣어서 풀었다.

말 순서 정하기

10개의 주사위 결과를 4개의 말에게 분배하는 모든 경우의 수를 구해야하기 때문에 중복순열을 이용했다.
말 4개는 vector m, 10개를 뽑으면 vector mm에 저장한다.

중복순열

vector<int> m = {0, 1, 2, 3}, mm(10);

void dfs(int cnt)
{
    if (cnt == 10)
    {
        //여기서 중복순열이 완성
        return;
    }
    for (int i = 0; i < m.size(); i++)
    {
        mm[cnt] = m[i];
        dfs(cnt + 1);
    }
}

int main()
{
	dfs(0);
}

점수 계산하기

중복순열을 만들었으면 함수 go()를 통해서 점수를 계산해준다.

말의 현재 위치를 배열 l에 저장하고
칸에 말의 유무는 배열 visited에 저장한다.

만약 이동하는 말의 위치 location이 파란 화살표가 있는 칸일 때는 맵의 규칙에 따라 위치를 바꿔준다.

이동을 마쳤을 때 위치의 visited값이 1이면 이 주사위 순열은 불가능하므로 -1을 return한다.

아니라면 visited[출발위치] = 0
visited[도착위치] = 1
l[이동한 말] = location
res += v[location]

go함수의 return값 중 최대값을 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> m = {0, 1, 2, 3}, mm(10), a(10), b, v(32);
int mx, l[4], visited[32];

int go()
{
    int res = 0;
    for (int i = 0; i < 10; i++)
    {
        int mal = mm[i];
        int st = l[mal];
        int location = l[mal];
        int flag = 0;

        for (int j = 0; j < a[i]; j++)
        {
            if (location == 5 && j == 0)
                location = 21;
            else if (location == 10 && j == 0)
                location = 27;
            else if (location == 15 && j == 0)
                location = 29;
            else if (location == 31 || location == 28)
                location = 24;
            else if (location == 26)
                location = 20;
            else if (location == 20)
            {
                flag = 1;
                break;
            }
            else
                location++;
        }

        if (visited[location])
            return -1;
        if (flag)
            visited[st] = 0;
        else
        {
            visited[st] = 0, visited[location] = 1;
            l[mal] = location;
            res += v[location];
        }
    }
    return res;
}

void dfs(int cnt)
{
    if (cnt == 10)
    {
        fill(&visited[0], &visited[0] + 32, 0);
        fill(&l[0], &l[0] + 4, 0);
        int tmp = go();
        mx = max(mx, tmp);
        return;
    }
    for (int i = 0; i < m.size(); i++)
    {
        mm[cnt] = m[i];
        dfs(cnt + 1);
    }
}

int main()
{
    for (int i = 0; i < 10; i++)
        cin >> a[i];
    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;
    dfs(0);
    cout << mx << "\n";
}