[백준 17825] 주사위 윷놀이

주사위 윷놀이

Algorithm: dfs, 시뮬레이션 Created: Apr 21, 2020 3:11 PM DoubleChk: No Type: 백준 link: https://www.acmicpc.net/problem/17825

문제

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

https://upload.acmicpc.net/43409ac6-54bf-4a21-b542-e01a8211e59f/-/preview/

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

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

---

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <iostream>
using namespace std;
map<int, int> red = {
        { 0, 2 },{ 2, 4 },{ 4, 6 },
        { 6, 8 },{ 8, 10 },{ 10, 12 },
        { 12, 14 },{ 14, 16 },{ 16, 18 },
        { 18, 20 },{ 20, 22 },{ 22, 24 },
        { 24, 26 },{ 26, 28 },{ 28, 30 },
        { 30, 32 },{ 32, 34 },{ 34, 36 },
        { 36, 38 },{ 38, 40 },{ 40, 50 }
};

map<int, int> blue = {
        { 10, 13 },{ 13, 16 },{ 16, 19 },
        { 19, 25 },{ 20, 22 },{ 22, 24 },
        { 24, 25 },{ 30, 28 },{ 28, 27 },
        { 27, 26 },{ 26, 25 },
};

map<int, int> blue_goal = {
        { 25, 30 },{ 30, 35 },{ 35, 40 },{ 40, 50 }
};

int ans;
vector<int> dice;
void input(){
    for(int i=0; i<10; i++){
        int n;
        cin >> n;
        dice.push_back(n);
    }
}
int move(int idx, int piece, vector<pair<int, int>>& pieces){

    //해당 piece의 방향 알기
    int dir = pieces[piece].second;
    int now = pieces[piece].first;
    int cnt = dice[idx];

    for(int i=0; i<cnt; i++){

        if(dir == 0){
            now = red[now];
        }else if(dir == 1){
            now = blue[now];
        }else if(dir == 2){
            now = blue_goal[now];
        }

        if(now == 25) dir = 2;
        else if(now == 50) break; //끝에 도달
    }

    int check = true;
    if(now == 50){
        pieces[piece].first = 50;
    }else{

        if(dir == 0 && (now == 10 || now == 20 || now == 30)) dir = 1;

        for(int i=0; i<4; i++){ //중복된 말이 있는지 체크한다.
            if(i == piece) continue;
            if(pieces[i].first == now && (now == 40 || dir == pieces[i].second)){
                check = false;
            }
        }

        if(!check){
            return -1;
        }else{
            pieces[piece].first = now;
            pieces[piece].second = dir;
            return now;
        }

    }

    return 0;
}
void solve(int idx, int sum, vector<pair<int, int>>& pieces){

    if(idx >= 10){
        ans = max(ans, sum);
        return;
    }

    //모든 말들 dfs
    for(int i=0; i<4; i++){
        int prev = pieces[i].first;
        int prev_dir = pieces[i].second;

        int ret = move(idx, i, pieces);
        if(ret > -1){
            solve(idx + 1, sum + ret, pieces);
        }

        pieces[i].first = prev;
        pieces[i].second = prev_dir;
    }

}
int main(){
    vector <pair<int, int>> pieces; //현재 위치, 방향
    //0 -> 제일 큰 동그라미
    //1 -> 꺾을 때
    //2 -> 25일 때

    pieces ={{0, 0},{0, 0},{0, 0},{0, 0}};

    input();
    solve(0, 0, pieces);

    cout << ans << endl;

    return 0;
}

• 문제 풀이

  map을 사용해서 윷놀이 판을 구현한다.

  4개의 말을 10번 돌리는 모든 경우의 수를 파악하여 제일 큰 값을 저장해야 하기 때문에, dfs로 풀어준다.