[백준][구현][백트래킹] 17825 주사위 윷놀이 c++구현

목차

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

문제

 

문제 구현 방향

인접리스트에 저장해놓고 말 4개를 백트래킹하는 방식으로 구현했다.

말 4개를 10번 움직이는 것이므로 4^10이라는 탐색 시간은 충분히 구현할 수 있다.

 

 

 

문제 구현 시 주의점

1. 말이 모일 때 예외처리를 매우 잘해주어야 한다. (25, 30, 35, 40)
2. 도착지에 가면 말은 바로 멈춘다는 사실도 주의해야 한다.
3. 또한 도착지에는 말이 여러개 갈 수 있다는 사실을 주의해야 한다.

 

 

코드 구현

#include <iostream>
#include <vector>

using namespace std;

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

vector<int> arr;

int msum = 0;
vector<pair<int, int>> horse = { {0,0}, {0,0}, {0, 0}, {0,0} };
void game(int here, int sum) {
    if (here == 10) {
        msum = max(sum, msum);

        return;
    }
    for (int i = 0; i < 4; i++) {
        int cura = horse[i].first;
        int curb = horse[i].second;
        int a = horse[i].first;
        int b = horse[i].second + arr[here];
        int flag = 0;
        if ((cura == 0 && curb == 21) || (cura == 1 && curb == 8) || (cura == 2 && curb == 7) || (cura == 3 && curb == 8))
            continue;
        if (a == 0 && b == 5) {
            a = 1;
            b = 0;
        }
        else if (a == 0 && b == 10) {
            a = 2;
            b = 0;
        }
        else if (a == 0 && b == 15) {
            a = 3; 
            b = 0;
        }

        if (a == 0 && b >= 21) 
            b = 21;
          
        else if (a == 1 && b >= 8)
            b = 8;
       
        else if (a == 2 && b >= 7)
            b = 7;
       
        else if (a == 3 && b >= 8) 
            b = 8;
        
		//모든 예외처리를 다 해주었다....
        //더 효율적으로 풀 수 있을 것 같은데..
        for (int j = 0; j < 4; j++) {
            if (j != i) {
                if (horse[j].first == a && horse[j].second == b)
                    flag = 1;
                if (a == 0) {
                    if (horse[j].first == 1 && horse[j].second == 7 && b == 20) {
                            flag = 1;
                    }
                    else if (horse[j].first == 2 && horse[j].second == 6 && b == 20) {
                            flag = 1;
                    }
                    else if (horse[j].first == 3 && horse[j].second == 7 && b == 20) {
                        flag = 1;
                    }
                }
                if (a == 1) {
                    if (horse[j].first == 2 && horse[j].second >=3) {
                        if (horse[j].second + 1 == b)
                            flag = 1;
                    }
                    else if (horse[j].first == 3 && horse[j].second >= 4) {
                        if (horse[j].second == b)
                            flag = 1;
                    }
                    else if (horse[j].first == 0 && horse[j].second == 20 && b == 7) {
                        flag = 1;
                    }
                }
                else if (a == 2) {
                    if (horse[j].first == 1 && horse[j].second >= 4) {
                        if (horse[j].second == b+1)
                            flag = 1;
                    }
                    else if (horse[j].first == 3 && horse[j].second >= 4) {
                        if (horse[j].second == b+1)
                            flag = 1;
                    }
                    else if (horse[j].first == 0 && horse[j].second == 20 && b == 6) {
                        flag = 1;
                    }
                }
                else if (a == 3) {
                    if (horse[j].first == 2 && horse[j].second >= 3) {
                        if (horse[j].second + 1 == b)
                            flag = 1;
                    }
                    else if (horse[j].first == 1 && horse[j].second >= 4) {
                        if (horse[j].second == b)
                            flag = 1;
                    }
                    else if (horse[j].first == 0 && horse[j].second == 20 && b == 7) {
                        flag = 1;
                    }
                }
            }
        }
        if ((a == 0 && b == 21) || (a == 1 && b == 8) || (a == 2 && b == 7) || (a == 3 && b == 8))
            flag = 0;
        if (flag)
            continue;
  
        horse[i].first = a;
        horse[i].second = b;
        sum += v[a][b];
        
        game(here + 1, sum);


        sum -= v[a][b];
        horse[i].first = cura;
        horse[i].second = curb;

    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int num;
    for (int i = 0; i < 10; i++) {
        cin >> num;
        arr.push_back(num);
    }
    game(0, 0);
    cout << msum;
    return 0;
}