[BOJ] 17825 : 주사위 윷놀이

문제 링크

17825번: 주사위 윷놀이 (acmicpc.net)

17825번: 주사위 윷놀이

주사위로 진행되는 윷놀이를 규칙대로 구현하는 문제.

풀이

왼쪽과 같은 윷놀이 판을 어떻게 구현할지가 일단 첫번째 문제였다. 파란색 칸을 밟았을 때 경로가 바뀌는 것을 어떻게 표현해야하지 생각하다가, 처음엔 10, 20, 30 칸을 밟을때마다 경로가 바뀌니까 4가지 경우의 경로를 따로 만들려고 했었다. 하지만 그렇게하면 이동할 칸에 이미 말이있는지 파악하기가 힘들었다.

그래서 나는 내 임의대로 각 칸마다 번호를 부여했다.

 

 

 

이렇게 각 칸마다 내 마음대로 번호를 부여하고

다음 칸의 번호를 Next라는 배열을 만들어서 미리 정해두었다.

예를 들어 31번칸 다음칸은 24번칸인데 이런 경우는 이동이 불규칙적이기 때문에 31번 다음칸은 24번이라고 미리 경로를 정해서 구현했다.

만약 이동하려할 때 시작칸이 5번, 10번, 30번이면 다음칸이 각 21, 27, 29번칸이 되도록 했다.

이렇게 하게되면 경로를 하나하나 지정해주어야 한다는 단점이 있고, 코드가 조금 지저분해진다. 하지만 이것말고 다르게 구현할 방법이 생각이 안나서 이렇게 했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 30 + 5;
int N, M, T;
int Score[MAX_N];
int Next[MAX_N];
int horse[4];
int Turn[11];
int ans = -1;
 
void Init();
int Move_horse(int horse_num, int moving);
bool is_ok(int next);
void backtracking(int depth, int total_Score);
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    Init();
    for (int i = 0; i < 10; i++)
        cin >> Turn[i];
    backtracking(0, 0);
    cout << ans << "\n";
    return 0;
}
 
void Init() {
    for (int i = 1; i <= 20; i++)
        Score[i] = 2 * i;
    Score[27] = 22;
    Score[28] = 24;
    Score[21] = 13;
    Score[22] = 16;
    Score[23] = 19;
    for (int i = 0; i <= 2; i++)
        Score[24 + i] = 25 + 5 * i;
    for (int i = 0; i <= 2; i++)
        Score[29 + i] = 28 - i;
    for (int i = 0; i <= 31; i++)
        Next[i] = i + 1;
    Next[20] = INF;
    Next[31] = Next[28] = 24;
    Next[26] = 20;
}
 
int Move_horse(int horse_num, int moving) {
    int now = horse[horse_num];
    if (now == 5) {
        now = 21;
        moving--;
    }
    else if (now == 10) {
        now = 27;
        moving--;
    }
    else if (now == 15) {
        now = 29;
        moving--;
    }
 
    while (moving--) {
        now = Next[now];
        if (now == INF) {
            now = -1;
            break;
        }
    }
    return now;
}
 
bool is_ok(int next) {
    for (int i = 0; i < 4; i++)
        if (horse[i] != -1 && horse[i] == next)
            return false;
    return true;
}
 
void backtracking(int depth, int total_Score) {
    if (depth == 10) {
        ans = max(ans, total_Score);
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (horse[i] == -1)
            continue;
        int next = Move_horse(i, Turn[depth]);
        if (is_ok(next)) {
            int temp = horse[i];
            horse[i] = next;
            if (next == -1)
                backtracking(depth + 1, total_Score);
            else backtracking(depth + 1, total_Score + Score[next]);
            horse[i] = temp;
        }
    }
}

이동이 끝난 말은 위치를 -1로 지정해서 도착했음을 표현했다.

말의 위치가 -1인 말은 더이상 이동을 하지 않는다.