백준 17825 주사위 윷놀이

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

 

 

게임 규칙 :

• 10번의 주사위 값이 주어지며, 각 턴마다 말 하나를 골라 주사위에 나온 만큼 이동
• 말은 빨간색 화살표(기본 경로)를 따라 이동하며, 파란색 화살표 전환 지점에서 새로운 경로로 진입 가능
• 도착 칸에 도달하면 해당 말은 게임에서 더 이상 움직일 수 없음
• 이동한 칸에 다른 말이 있을 경우, 그 칸으로 이동할 수 없습니다. 단, 도착 칸은 제외
• 각 턴마다 이동한 칸의 점수를 합산하며, 점수의 최대값 리턴

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int d[10]; // d[i]: i번째 턴에서 주사위 값
int p[4]; // p[i]: i번째 말의 현재 위치
int nxt[34];  // nxt[i]: 칸 i에서 빨간 화살표를 따라 다음 칸으로 이동
int val[34];  // val[i]: 칸 i의 점수
int blue[34]; // blue[i]: 칸 i가 파란 화살표 전환 지점이면 다음 칸을 가리킴
bool occupied[34]; // occupied[i]: 칸 i에 말이 있으면 true, 없으면 false
int maxScore = INT_MIN;

void solve(int cnt, int sum)//백트랙킹 함수 
{
    if (cnt == 10)  // 종료 조건: 주사위를 10번 던진 경우
    {
        maxScore = max(maxScore, sum);
        return;
    }

    for (int i = 0; i < 4; i++) // 4개의 말 중 하나를 선택
    {
        int prev = p[i]; // 현재 말의 위치 저장
        int cur = prev; // 이동 후 위치를 저장할 변수
        int move = d[cnt]; // 이번 턴에서 주사위 값

        if (blue[cur] > 0) // 현재 위치가 파란 화살표 위 인가??
        { 
            cur = blue[cur]; // 파란 화살표를 따라 이동
            move--;          // 파란 화살표로 전환했으니 남은 이동 횟수 감소
        }

        while (move-- && cur != 21) // 도착 칸(21)에 도달하면 이동 중단
        {
            cur = nxt[cur]; // 빨간 화살표를 따라 이동
        }

		// 이동한 칸에 다른 말이 있다면 이동 불가능! (도착 칸 제외)
        if (cur != 21 && occupied[cur]) continue;
		
        //상태 업데이트 : 현재 위치에서 이동한 칸으로 말 이동
        occupied[prev] = false; // 이전 위치는 더 이상 점유되지 않음
        occupied[cur] = true; // 이동한 위치는 새로 점유됨
        p[i] = cur; // 말의 현재 위치를 업데이트

        solve(cnt + 1, sum + val[cur]); //다음 턴으로 진행하며 점수를 합산

		//상태 복구 
        p[i] = prev; //말 이전 위치로
        occupied[prev] = true; //이전위치 상태 true로 하고
        occupied[cur] = false; // 이동한 위치의 상태는 다시 false
    }
}

void init() 
{
    // 빨간 화살표 경로 설정 (기본 경로)
    for (int i = 0; i < 21; i++) nxt[i] = i + 1; // 0~20까지는 다음 칸으로 이동
    nxt[21] = 21; // 도착 칸(21)은 자기 자신으로 이동

	// 파란 화살표 경로 설정
    nxt[22] = 23; nxt[23] = 24; nxt[24] = 25; nxt[25] = 26;
    nxt[26] = 27; nxt[27] = 20;
    nxt[28] = 29; nxt[29] = 30; nxt[30] = 25;
    nxt[31] = 32; nxt[32] = 25;

	// 파란 화살표 전환되는 곳
    blue[5] = 22; blue[10] = 31; blue[15] = 28;

    for (int i = 0; i < 21; i++) val[i] = i * 2; // 기본 경로의 점수 (2의 배수)
    val[22] = 13; val[23] = 16; val[24] = 19;
    val[25] = 25; val[26] = 30; val[27] = 35; // 파란 화살표 경로의 점수
    val[28] = 28; val[29] = 27; val[30] = 26;
    val[31] = 22; val[32] = 24;
}

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

    solve(0, 0);
    cout << maxScore << endl;
    return 0;
}