17825-주사위 윷놀이

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다.

 

솔루션을 참고하여 풀었으나 완전히 이해하고 푸는데 이틀씩이나 걸린 문제입니다.

 

해당 문제는 총 10차례동안 나온 주사위 값을 토대로 4마리의 말을 움직여 문제 규칙에따라 얻을 수 있는 점수의 최댓값을 출력하는 문제입니다.

 

저는 브루트 포스 알고리즘을 이용하여 해당 문제를 풀었습니다. 즉, 각 차례별로 나온 주사위 값에따라 4마리의 말을 모두 움직여가며 모든 경우의 수를 다 탐색하였습니다.

 

구현에 있어 어려웠던 점은 윷놀이판의 구조가 직사각형 형태가 아니여서 프로그램상에서 어떻게 구현해야할지를 떠올리는 것이 어려웠습니다. 한참을 생각해보다가 윷놀이판의 구조를 그래프 자료구조를 이용하면 구현할 수 있겠다 싶었습니다. 윷놀이판의 구조를 적절한 자료구조를 이용하여 구현하는것이 이 문제의 핵심이였다고 생각합니다.

 

먼저, 윷놀이판의 한 칸을 그래프를 구성하는 하나의 노드로 정의하였습니다. 아래의 그림상에서 윷놀이판의 각 칸위에 적힌 숫자를 노드의 번호(=ID)로 정의하였습니다. 각 노드간의 연결관계를 정의하기 위하여 2차원 vector 를 사용하였습니다(0(시작)->1, 1->2, 2->3, 3->4, 4->5, 5->{22, 6}, ... 20->21(도착)). 또한 노드별로 칸에 맞는 점수를 정의해주었습니다.

 

 

이렇게 그래프상으로 표현하고나서, 하나의 말이 N 칸을 간다고 하였을때, 노드간의 연결관계에따라 한칸 한칸씩 움직이며 N 칸을 가도록 구혔하였고, 만약 말의 시작지점이 파란색 칸의 해당하는 노드인 경우(프로그램상에서 연결된 노드가 두개인 경우를 체크하여 구현함), 처음 한칸은 파란색 엣지로 이어진 노드로 1칸을 간뒤 N-1칸을 건너가는 식으로 구현하였습니다. 그리고, N 칸을 건넜을때, 해당칸에 이미 말이 존재하는 경우, 해당 차례를 무효화하도록 구현하였습니다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

int dice[10];
int maximum_score = 0;

vector<vector<int>> connection_info;
int map[33];
bool ban[33]={false,};

int horses[4] = {0, 0, 0, 0}; //말의 위치 저장

void dfs(int turn, int cumulative_score)
{
    if(turn == 10)
    {
        maximum_score = max(maximum_score, cumulative_score);
        return ;
    }

    for(int i = 0; i < 4; i++)
    {
        if(horses[i] == 21) continue; // 이미 도착칸에 있다면 선택하지 않음

        int start_point = horses[i];
        int move_point = horses[i];
        int num_jump = dice[turn];

        if(connection_info[start_point].size() == 2) //말이 파란색칸에 서있다면
        {
            move_point = connection_info[start_point][1]; //파란색 화살표를 타고 감
            num_jump -= 1;
        }

        while(num_jump--) move_point = connection_info[move_point][0]; // 다음칸으로 이동
        
        if(move_point == 21 or ban[move_point] == false) // 이동할 수 있는지 체크
        {
            ban[start_point] = false; // 이동할거니까 false 로 만들어줌
            ban[move_point] = true;
            horses[i] = move_point;
            dfs(turn + 1, cumulative_score + map[horses[i]]);
            horses[i] = start_point; // 해당 경우의 수 탐색 끝났으면 다시 말 원위치
            ban[move_point] = false;
            ban[start_point] = true;
        }
    }
        
}

int main()
{
    connection_info.resize(33);

    map[21] = 0;
    for(int i = 0; i <= 20; i++)
    {
        connection_info[i].push_back(i+1);
        map[i] = i*2;
    }

    connection_info[5].push_back(22);
    map[22] = 13;
    connection_info[22].push_back(23);
    map[23] = 16;
    connection_info[23].push_back(24);
    map[24] = 19;
    connection_info[24].push_back(25);
    map[25] = 25;

    connection_info[25].push_back(26);
    map[26] = 30;
    connection_info[26].push_back(27);
    map[27] = 35;
    connection_info[27].push_back(20);

    connection_info[10].push_back(28);
    map[28] = 22;
    connection_info[28].push_back(29);
    map[29] = 24;
    connection_info[29].push_back(25);

    connection_info[15].push_back(30);
    map[30] = 28;
    connection_info[30].push_back(31);
    map[31] = 27;
    connection_info[31].push_back(32);
    map[32] = 26;
    connection_info[32].push_back(25);

    connection_info[21].push_back(21); //도착칸에 도착하면 순회하도록

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("17825.txt", "r", stdin);
    for(int i = 0; i < 10; i++) cin >> dice[i];
    dfs(0, 0);
    cout << maximum_score;
    return 0;
}