[ BOJ - 17825번 ] 주사위 윷놀이 (C++)

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

 시간 제한이 2초이고, 4개의 말을 10번 움직이는 경우의 수는 4¹⁰이기 때문에 모든 경우를 탐색하여 문제를 해결할 수 있다.

 

[ 풀이 방법 ]

1. 윷놀이 판 생성 기능

  - 4가지 경로를 생성한다.

     경로 1: 시작 - 10 - 20 - 30 - 40 - 도착 

     경로 2: 시작 - 10 - 25 - 40 - 도착 

     경로 3: 시작 - 10 - 20 - 25 - 40 - 도착 

     경로 4: 시작 - 10 - 20 - 30 - 25 - 40 - 도착 

  - 경로의 각 위치에는 점수가 저장된다.

vector<int> board[4] = {
    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0},
    {0, 2, 4, 6, 8, 10, 13, 16, 19, 25, 30, 35, 40, 0},
    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 25, 30, 35, 40, 0},
    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 28, 27, 26, 25, 30, 35, 40, 0}
};

 

  - 이 때, 10, 20, 30, 40은 모든 경로에 포함되고 25, 30, 35는 경로 2, 3, 4에 모두 포함된다.

    - 각 경로의 중복 위치를 map에 저장해 중복되는 위치를 파악할 수 있게 한다.

map<pair<int, int>, vector<pair<int, int>>> common

 

2. 말 이동 기능

  - 재귀함수와 for문을 이용해 말이 이동할 수 있는 모든 경우를 탐색한다.

    - 4마리 말의 경로와 위치를 저장하는 배열이 필요하다.

    - 주사위 결과에 따라 말을 이동한다.

    - 생성해둔 윷놀이 판과 중복 위치 map을 이용해 점수 계산과 중복 칸 방문 처리를 수행한다.

    - visited 배열을 이용해 이동할 수 없는 경우(이동할 칸에 이미 말이 있는 경우)를 처리한다.

    - 경로 1번의 10, 20, 30 위치에 정확히 도달할 경우, 다음 이동 순서에 경로 2, 3, 4로 경로를 바꾸어 이동한다.

 

[ 회고 ]

 처음에 중복되는 칸이 10, 20, 30의 위치만 있다고 생각하고 구현하여 정답을 맞추지 못했다.

디버깅에 오랜 시간이 걸려 중복되는 위치가 더 많다는 문제를 찾아낸 뒤에는 시간이 오래 지났고 구현 코드도 적합하지 않아 처음부터 다시 계획하고 구현해야 했다.

 또한 구현해야할 기능과 조건이 매우 복잡하다보니 구현할 때 실수도 많이해 디버깅과 구현에 오랜 시간이 걸렸다.

특히 처음에 중복 위치의 방문 처리와 방문 취소 기능을 어떻게 구현할 지 확실하게 계획하지 않고 구현하여, 정확하고 보기 쉬운 코드로 구현하지 못하고 하드코딩하게 되었고, 정확한 구현과 오류 위치 파악이 어려워 구현과 디버깅에 어려움을 겪었다.

 

 문제 이해를 정확히 하지 못했고, 계획 단계에서 구현을 어떻게 해야할 지 구체적으로 생각하고 검증하지 않아 풀 수 없었던 문제였다.

앞으로는 문제 이해와 풀이 계획, 검증에 더 오랜 시간을 사용해야 할 것이다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

typedef pair<int, int> Horse;

vector<int> board[4] = {
    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0},
    {0, 2, 4, 6, 8, 10, 13, 16, 19, 25, 30, 35, 40, 0},
    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 25, 30, 35, 40, 0},
    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 28, 27, 26, 25, 30, 35, 40, 0}
};
vector<bool> visited[4];
int dice[10];

map<Horse, vector<Horse>> common;
vector<Horse> horses = {make_pair(0, 0), make_pair(0, 0), make_pair(0, 0), make_pair(0, 0)};

int res;

void init() {
    
    common[make_pair(0, 5)] = common[make_pair(1, 5)] = common[make_pair(2, 5)] = common[make_pair(3, 5)] = {make_pair(0, 5), make_pair(1, 5), make_pair(2, 5), make_pair(3, 5)};
    
    common[make_pair(0, 10)] = common[make_pair(1, 10)] = common[make_pair(2, 10)] = common[make_pair(3, 10)] = {make_pair(0, 10), make_pair(1, 10), make_pair(2, 10), make_pair(3, 10)};
    
    common[make_pair(0, 15)] = common[make_pair(1, 15)] = common[make_pair(2, 15)] = common[make_pair(3, 15)] = {make_pair(0, 15), make_pair(1, 15), make_pair(2, 15), make_pair(3, 15)};
    
    common[make_pair(0, 20)] = common[make_pair(1, 12)] = common[make_pair(2, 16)] = common[make_pair(3, 22)] = {make_pair(0, 20), make_pair(1, 12), make_pair(2, 16), make_pair(3, 22)};
    
    for(int i = 0; i < 3; i++) {
        vector<Horse> t;
        t.push_back(make_pair(1, 9+i));
        t.push_back(make_pair(2, 13+i));
        t.push_back(make_pair(3, 19+i));
        
        for(int j = 0; j < t.size(); j++) {
            common[t[j]] = t;
        }
        
        vector<Horse>().swap(t);
    }
    
    for (int i = 0; i < 4; i++) {
        visited[i].resize(board[i].size());
    }
    
    for (int i = 0; i < 10; i++) {
        cin >> dice[i];
    }
}

void solve(int cnt, int score) {
    if(cnt >= 10) {
        if(res < score) {
            res = score;
        }
        return;
    }
    
    for(int i = 0; i < 4; i++) {
        
        int road = horses[i].first;
        int pos = horses[i].second;
        
        if(pos == int(board[road].size()) - 1) continue;
        
        int nRoad = road;
        int nPos = pos + dice[cnt];
        
        if(road == 0) {
            if(pos == 5) {
                nRoad = 1;
            } else if(pos == 10) {
                nRoad = 2;
            } else if(pos == 15) {
                nRoad = 3;
            }
        }
        
        int maxPos = int(board[nRoad].size())-1;
        if(nPos > maxPos) nPos = maxPos;
        
        if(nPos != maxPos && visited[nRoad][nPos]) {
            continue;
        }
        
        vector<Horse> commons = common[make_pair(road, pos)];
        vector<Horse> nCommons = common[make_pair(nRoad, nPos)];
        if(!commons.empty()) {
            for (int i = 0; i < commons.size(); i++) {
                visited[commons[i].first][commons[i].second] = false;
            }
        } else visited[road][pos] = false;
        if(!nCommons.empty()) {
            for (int i = 0; i < nCommons.size(); i++) {
                visited[nCommons[i].first][nCommons[i].second] = true;
            }
        } else visited[nRoad][nPos] = true;
        
        horses[i].first = nRoad;
        horses[i].second = nPos;
        solve(cnt+1, score+board[nRoad][nPos]);
        horses[i].first = road;
        horses[i].second = pos;
        
        if(!commons.empty()) {
            for (int i = 0; i < commons.size(); i++) {
                visited[commons[i].first][commons[i].second] = true;
            }
        } else visited[road][pos] = true;
        if(!nCommons.empty()) {
            for (int i = 0; i < nCommons.size(); i++) {
                visited[nCommons[i].first][nCommons[i].second] = false;
            }
        } else visited[nRoad][nPos] = false;
        
        vector<Horse>().swap(commons);
        vector<Horse>().swap(nCommons);
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    init();
    
    solve(0, 0);
    
    cout << res << '\n';
    
    return 0;
}