백준 17825: 주사위 윷놀이(c++, 구현 & 백트래킹)

사용 언어	티어	시간 제한	메모리 제한
c++		2초	512MB

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

17825번: 주사위 윷놀이

 

#0 문제

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

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

 

#1 입력

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

 

#2 접근

• 우리가 일반적으로 아는 윷놀이와 같은 방식으로 진행된다. 다만 도착했을 때를 제외하고는, 한 칸에 여러 말이 동시에 존재할 수 없다.
• 10개의 턴으로만 이루어져있고, 10개의 턴에 나올 주사위의 숫자도 정해져있다.
• 선택해야할 것은 어떤 말을 이동시킬 것인가이다. 각 턴마다 4개의 말 중에 이동시킬 것을 고르는 것이기 때문에 $4^{10}$ 의 경우의 수를 가질 것이다. 백트래킹 완전탐색을 진행한다면 시간 내에 풀이할 수 있을 것이다.
• 윷놀이 판의 정보가 입력으로 들어오지 않기 때문에 적절히 index를 연결시켜서 새로운 형태의 배열로 바꾸는 것 역시 필요할 것이다.

 

#3 풀이

• 우선 윷놀이 판에 index를 붙이고 index -> next index 형태의 2차원 벡터로 변환했다.

• index에 맞춰서 점수 배열도 만들어준다.
• 파란색 화살표가 있는 경우에는 해당 index의 벡터의 두번째 원소로 넣어주었다. 이는 나중에 파란색에 도착했을 때, 해당 배열의 크기가 2이면 파란색이라고 판단하도록 하기 위함이다.
• 백트래킹으로 구현해본다.
  • 주사위 index가 10이면 다 던진 것이므로 최댓값을 갱신해준다.
  • 말이 존재하는 위치에서, 현재 주사위 숫자만큼 이동시킨다.
  • 파란색일 경우 파란색 방향으로 먼저 이동하고 나머지만큼 이동하면 된다.
  • 이동했을 때 말이 존재하면 안된다. 하지만 도착 칸이면 상관 없기 때문에, 이전 위치의 말은 지워주고 다음 주사위를 던진다.
  • 이동했을 때 말이 존재하면 다음 말을 확인해본다.
  • 이동할 수 있는 경우엔, 말의 위치를 이동시킨다.
    • 이때 시작점에서 이동한 말일 경우에는 시작지점의 남은 말의 개수를 하나 빼준다. 이때 이전 위치의 말은 지우지 않는다. 시작 지점의 말의 개수가 남아있는데 시작 지점의 말을 지우면 안된다. 그래서 남은 말의 개수로 판단한다. 점수는 더해서 백트래킹한다.
    • 아닐 경우에는 이전 위치의 말을 지워주고, 점수를 더해서 백트래킹한다.

 

#4 코드

/*
17825 주사위 윷놀이
구현, 백트래킹
*/

#include <iostream>
#include <vector>

#define START 0
#define END 21

using namespace std;


typedef pair<int, int> P;

vector<int> board[33];

int score[33] = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0, 13, 16, 19, 22, 24, 28, 27, 26, 25, 30, 35};
int dice[10];
int ans;

int Max(int a, int b) { return a > b ? a : b; }


// 시작 지점의 말의 개수, pos는 말의 위치
void backtracking(int horse, int dice_idx, vector<int> horse_pos, int score_sum) {
    if (dice_idx == 10) {
        
        ans = Max(ans, score_sum);
        return;
    }

    // 도착말은 이동 못하니까 제외
    for (int i = 0; i < 33; ++i) {
        if (horse_pos[i]) {
            // 시작 말의 개수가 0일 경우에는 시작점은 선택 못하니까 건너뛴다.
            if (horse == 0 && i == 0) {
                continue;
            }

            int move = dice[dice_idx];

            int cur = i;

            if (board[cur].size() == 2) {
                // 파란색 길로 가야함
                cur = board[cur][1];
                // 횟수 하나 감소
                move--;
            }
            for (int j = 0; j < move; ++j) {
                cur = board[cur][0];
            }

            // 이동했을 때 말이 존재하면 안됨! 도착 칸이면 상관 없음
            if (cur == END) {
                vector<int> new_horse_pos = horse_pos;
                new_horse_pos[i] = 0;
                // 이동을 마쳤으므로 다음 주사위를 던져본다.
                backtracking(horse, dice_idx + 1, new_horse_pos, score_sum);
            } else if (horse_pos[cur]) {
                // 칸에 말이 존재하므로 다음 말을 선택해봄
                continue;
            } else {
                // 이동할 수 있는 경우
                vector<int> new_horse_pos = horse_pos;
                new_horse_pos[cur] = 1;
                
                if (i == 0) {
                    // 시작점에서 이동한 경우 남은 말의 수를 하나 빼고 넘겨줌
                    backtracking(horse - 1, dice_idx + 1, new_horse_pos, score_sum + score[cur]);
                } else {
                    new_horse_pos[i] = 0;
                    backtracking(horse, dice_idx + 1, new_horse_pos, score_sum + score[cur]);
                }
            }
        }
    }
}




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


    //start = 0, end = 21
    for (int i = 0; i < 21; ++i) {
        board[i].push_back(i + 1);
    }

    board[21].push_back(21);

    board[5].push_back(22);
    board[22].push_back(23);
    board[23].push_back(24);
    board[24].push_back(30);

    board[10].push_back(25);
    board[25].push_back(26);
    board[26].push_back(30);

    board[15].push_back(27);
    board[27].push_back(28);
    board[28].push_back(29);
    board[29].push_back(30);

    board[30].push_back(31);
    board[31].push_back(32);
    board[32].push_back(20);

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


    vector<int> horse_pos(33, 0);
    horse_pos[0] = 1;

    backtracking(4, 0, horse_pos, 0);

    cout << ans;


    return 0;
}