주사위 윷놀이

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0758 ~ 1225
// 4^10 = 약 100만
vector<int> arr(10);
int road[5][30];
bool vis[5][30];
vector<pair<int,int>> v(4); // 현재 로드의 인덱스, 현재 경로 번호
int ans;
void DFS(int depth, int tot){
    /* base 컨디션 */
    if(depth == 10){
        ans = max(ans, tot);
        return;
    }
    for(int ch=0;ch<4;ch++)
    {
        /* 도착지점에 있는 말은 패스 */
        if(v[ch].first != -1)
            if(road[v[ch].second][v[ch].first] == -1) continue;

        auto preV = v[ch];
        int nRoad = v[ch].second;
        /* 파란색 지점을 처리하기 위한 부분 */
        if(road[nRoad][v[ch].first] == 10){
            nRoad = 1;
            v[ch].first = -1;
        }
        else if(road[nRoad][v[ch].first] == 20)
        {
            nRoad = 2;
            v[ch].first = -1;
        }
        else if(nRoad == 0 and road[nRoad][v[ch].first] == 30)
        {
            nRoad = 3;
            v[ch].first = -1;
        }
        v[ch].second = nRoad;
        bool flag = false;
        for(int i=0;i<arr[depth];i++)
        {
            v[ch].first++;
            if(road[nRoad][v[ch].first] == -1) {
                flag = true;
                break;
            }else if(road[nRoad][v[ch].first] == -3){
                /* 3 경로의 접점인 25에 도착했을 때 */
                nRoad = 4;
                v[ch].second = 4;
                v[ch].first = 0;
            }else if(road[nRoad][v[ch].first] == -4){
                /* 0번 road를 타고 40 위치에 왔을 때 */
                nRoad = 4;
                v[ch].second = 4;
                v[ch].first = 3;
            }
        }
        /* 실행중 말이 종료지점에 도달했을 때 */
        if(flag == true) {
            vis[preV.second][preV.first] = false;
            DFS(depth+1, tot);
            vis[preV.second][preV.first] = true;
            v[ch] = preV;
            continue;
        }

        /* 말을 놓을 곳에 말이 존재하지 않아아야 둘 수 있다 */
        if(!vis[nRoad][v[ch].first])
        {
            int tmp_tot = tot + road[nRoad][v[ch].first];
            if(preV.first != -1)
                vis[preV.second][preV.first] = false;
            vis[nRoad][v[ch].first] = true;

            DFS(depth+1, tmp_tot);

            if(preV.first != -1)
                vis[preV.second][preV.first] = true;
            vis[nRoad][v[ch].first] = false;
        }

        /* 원상 복귀 */
        v[ch] = preV;
    }
}
void Init(){
    /* 0번 도로 */
    for(int i=0;i<19;i++)
        road[0][i] = (i+1)*2;
    road[0][19] = -4;
    /* 1번 도로 */
    road[1][0] = 13; road[1][1] = 16;
    road[1][2] = 19; road[1][3] = -3;
    /* 2번 도로 */
    road[2][0] = 22; road[2][1] = 24;
    road[2][2] = -3;
    /* 3번 도로 */
    road[3][0] = 28; road[3][1] = 27;
    road[3][2] = 26; road[3][3] = -3;
    /* 4번 도로 */
    road[4][0] = 25; road[4][1] = 30;
    road[4][2] = 35; road[4][3] = 40;
    road[4][4] = -1; 
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Init();
    /* Input */
    for(int i=0;i<10;i++)
        cin >> arr[i];
    for(int i=0;i<v.size();i++)
        v[i] = {-1, 0};
    DFS(0,0);
    cout << ans;
    return 0;
}

• 핵심
  • 이미 말이 있는 곳에는 말을 둘 수 없다
  • 윷놀이의 모든 경로를 5가지로 분리하여 이미 말이 있는 곳에 두지 않게 해야 한다
    --> 경로를 분리할 때 만약 겹치는 부분이 존재하면 무조건 오답
    • 1) 2 ~ 38
    • 2) 13 ~ 19
    • 3) 22 ~ 24
    • 4) 28 ~ 26
    • 5) 25 ~ 도착

• 오래걸린 이유
  • 문제풀이에 오기가 붙어서 4시간이나 풀었는데 핵심 문제점은 다음과 같다
    1) 아래 뜻을 오해석 해서 말이 있어도 이동은 할 수 있지만 이미 있던 말은 다음 턴에 고를 수 없다고 인지함
    --> 문제의 의도는 그냥 말이 있는 곳에 다른 말을 둘 수 없는 것임
  • 갈 수 있는 경로를 road 변수로 나누었는데 겹치는 부분이 존재하여 방문 체크가 누락되어 오답이 출력
    --> 충분히 생각해서 문제풀이 접근을 확실하게 한 뒤에 해야한다