[백준-삼성SW역량테스트 기출] 17825번. 주사위 윷놀이 C++

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

 

> 문제 설명

문제

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

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

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

입력

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

출력

얻을 수 있는 점수의 최댓값을 출력한다.

 

풀이

말판에서 10, 20, 30 꺾는 부분 맵은 따로 저장해줬다. (special 배열)

i = (1 or 2 or 3) 이라 했을 때, 각 맵 점수는 special[i][j] / (i*100) ( j는 현재 위치 ) 이다.

 

말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다.

이 조건을 지켜주기 위해, mapInfo랑 specInfo를 만들어서 체크해줬다.

specInfo의 각 인덱스마다 겹치는 부분(말판에서 25, 30, 35, 40) 과 mapInfo랑 specInfo랑 겹치는 부분(말판에서 40) 을 생각하지 못하고 이렇게 만들었었다..

따라서 겹치는 부분에 대해서 또 따로 체크를 더 해줬다.

 

움직이는 게 가능한 말에 대해서 움직이고( horse 정보와 mapInfo/specInfo 값 바꿈 )  재귀로 넣어준다.

돌아오면 움직일 때 바꿔줬던 정보에 대해 다시 돌려준다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;

int num[10];
//꺾는 부분
int special[3][7] = {{113, 116, 119, 125, 130, 135, 140}
                    , {222, 224, 225, 230, 235, 240}
                    , {328, 327, 326, 325, 330, 335, 340}};
int horse[4] = {0, 0, 0, 0};
bool mapInfo[42] = {false , };
bool specInfo[3][8] = {false, };
int maxPoint = -1;

void initialize(){

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

void move(int depth, int point){

    if(depth == 10){
        maxPoint = max(maxPoint, point);
        return;
    }

    int add = num[depth];

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

        //말이 갈 수 없는 경우
        //도착 칸에 있는 말
        //이동 마치는 위치에 다른 말이 있는 경우 ( 도착 칸- (-1) 제외 )

        int score = 0;
        int nextStep = 0;
        int index = 0;
        int nowloc = horse[i];
        int loc = 0;
        int bound = 0;

        if(horse[i] == -1) continue;

        if(horse[i]>=100){ // 파란 칸 처리
            index = (horse[i]/100)-1;

            loc = horse[i] - (index+1)*100;
            bound = 7;
            if(index == 1){
                bound = 6;
            }
            //bound 넘을 경우
            nextStep = loc + add;
            if( nextStep > bound){
                if(horse[i]%100 == 0){
                    mapInfo[horse[i]/20] = false;
                }
                else{
                    specInfo[index][loc] = false;
                }
                horse[i] = -1;
            }
            else{
                if(specInfo[index][nextStep]==true) continue;
                if(index==1 && nextStep >= 3){
                    if(specInfo[0][nextStep+1]==true || specInfo[2][nextStep+1]==true)
                        continue;
                }
                else if(index==0 && nextStep >= 4){
                    if(specInfo[1][nextStep-1]==true || specInfo[2][nextStep]==true)
                        continue;
                }
                else if(index==2 && nextStep >= 4){
                    if(specInfo[1][nextStep-1]==true || specInfo[0][nextStep]==true)
                        continue;
                }
                if((special[index][nextStep-1]-(index+1)*100) == 40){
                    if(mapInfo[20] == true) continue;
                }

                //지금 위치 표시 지워줌
                if(horse[i]%100 == 0){
                    mapInfo[horse[i]/20] = false;
                }
                else{
                    specInfo[index][loc] = false;
                }

                horse[i] = (index+1)*100 + nextStep;
                specInfo[index][nextStep] = true;  // 다음 갈 곳 표시해줌
                score = (special[index][nextStep-1]-(index+1)*100) ;
            }
        }

        else{ // 빨간 칸 일때
            nextStep = horse[i] + add;

            if(nextStep > 20){  // 도착!
                mapInfo[horse[i]] = false;
                horse[i] = -1;
            }
            else{
                if(mapInfo[nextStep]==true) continue;
                if(nextStep==20 && (specInfo[0][7]==true 
                        || specInfo[1][6]==true
                        || specInfo[2][7]==true)) continue;

                mapInfo[horse[i]] = false;   // 지금 위치 표시 지워줌
                horse[i] = nextStep;
                mapInfo[nextStep] = true; // 다음 갈 곳 표시해줌

                if(nextStep%5 == 0 && nextStep!=20){  // 꺾는 부분이면 값*20해서 저장해줌
                    int newStep = nextStep * 20; 
                    horse[i] = newStep;
                }
                score = nextStep*2;
            }
        }

        move(depth+1, point+score);

        //되돌려줌
        horse[i] = nowloc;

        if(horse[i]>=100){
            if(horse[i]%100 == 0){
                mapInfo[horse[i]/20] = true;
            }
            else{
                specInfo[index][loc] = true;
            }
            if(nextStep>bound) continue;
            specInfo[index][nextStep] = false;
        }
        else{
            mapInfo[horse[i]] = true;
            if(nextStep>20) continue;
            mapInfo[nextStep] = false;
        }

    }

    return;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    initialize();
    move(0, 0);

    cout<<maxPoint<<"\n";

    return 0;
}