[BOJ] 17825 - 주사위 윷놀이

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

17825번: 주사위 윷놀이

 

난이도

구현 + bfs / 난이도 ⭐️⭐️/ 1시간 35분

 

// board 0번째 줄 좌표 잘못 잡음
#include <stdio.h>
#include <vector>
using namespace std;

vector<vector<int> > board;
vector<int> dice;
int loc[4][2];
int check[5][22];

/*
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40
10 13 16 19 25
20 22 24 25
30 28 27 26 25
25 30 35 40

0 4 -> 1 0
0 9 -> 2 0
0 14 -> 3 0

1 4 -> 4 0
2 3 -> 4 0
3 4 -> 4 0

4 3 -> 0 18

*/
int answer;
void dfs(int dice_index, int sum)
{
    if (sum > answer)
    {
        answer = sum;
    }

    if (dice_index >= 10)
    {
        // printf("sum: %d\n", sum);
        return;
    }

    int x, y, newx, newy;
    for (int i = 0; i < 4; i++)
    {
        x = loc[i][0];
        y = loc[i][1];
        if (x == 0 && y > board[0].size() - 1)
        {
            continue;
        }

        newx = x;
        newy = y;

        if (newx == 0)
        {
            if (newy == 5)
            {
                newx = 1;
                newy = 0;
            }
            else if (newy == 10)
            {
                newx = 2;
                newy = 0;
            }
            else if (newy == 15)
            {
                newx = 3;
                newy = 0;
            }
        }

        for (int j = 0; j < dice[dice_index]; j++)
        {
            newy += 1;
            if (newx == 1 && newy == 4)
            {
                newx = 4;
                newy = 0;
            }
            else if (newx == 2 && newy == 3)
            {
                newx = 4;
                newy = 0;
            }
            else if (newx == 3 && newy == 4)
            {
                newx = 4;
                newy = 0;
            }
            else if (newx == 4 && newy == 3)
            {
                newx = 0;
                newy = board[0].size() - 1;
            }
        }

        // printf("%d %d\n", newx, newy);

        if (check[newx][newy] != -1)
        {
            continue;
        }

        if (newx == 0 && newy > board[0].size() - 1) // check point 2)
        {
            check[x][y] = -1;
            loc[i][0] = newx;
            loc[i][1] = newy;

            dfs(dice_index + 1, sum);

            loc[i][0] = x;
            loc[i][1] = y;
            check[x][y] = i;
        }
        else
        {
            check[x][y] = -1;
            check[newx][newy] = i;
            loc[i][0] = newx;
            loc[i][1] = newy;

            // printf("i, x, y: %d (%d %d), (%d %d)\n", i, x, y, newx, newy);
            //   dfs
            dfs(dice_index + 1, sum + board[newx][newy]);

            // reset
            loc[i][0] = x;
            loc[i][1] = y;
            check[newx][newy] = -1;
            check[x][y] = i;
        }
    }
}

void init()
{
    int temp;
    for (int i = 0; i < 10; i++)
    {
        scanf("%d", &temp);
        dice.push_back(temp);
    }

    vector<int> line1;
    for (int i = 0; i <= 40; i += 2)
    {
        line1.push_back(i);
    }
    board.push_back(line1);

    vector<int> line2;
    line2.push_back(10);
    line2.push_back(13);
    line2.push_back(16);
    line2.push_back(19);
    line2.push_back(25);
    board.push_back(line2);

    // 20 22 24 25
    vector<int> line3;
    line3.push_back(20);
    line3.push_back(22);
    line3.push_back(24);
    line3.push_back(25);
    board.push_back(line3);

    // 30 28 27 26 25
    vector<int> line4;
    line4.push_back(30);
    line4.push_back(28);
    line4.push_back(27);
    line4.push_back(26);
    line4.push_back(25);
    board.push_back(line4);

    // 25 30 35 40
    vector<int> line5;
    line5.push_back(25);
    line5.push_back(30);
    line5.push_back(35);
    line5.push_back(40);
    board.push_back(line5);

    // for (int i = 0; i < dice.size(); i++)
    // {
    //     printf("%d ", dice[i]);
    // }
    // printf("\n");

    // for (int i = 0; i < board.size(); i++)
    // {
    //     for (int j = 0; j < board[i].size(); j++)
    //     {
    //         printf("%d ", board[i][j]);
    //     }
    //     printf("\n");
    // }
    // printf("\n");
}

int main()
{
    // loc[4][2] = {0};
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 22; j++)
        {
            check[i][j] = -1;
        }
    }
    init();
    answer = 0;

    dfs(0, 0);
    printf("%d", answer);
}