[ 백준-17825번 / 완전 탐색 ] 주사위 윷놀이 (삼성기출)

1. 문제

---

 

17825번: 주사위 윷놀이

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1 복사

1 2 3 4 1 2 3 4 1 2

예제 출력 1 복사

190

예제 입력 2 복사

1 1 1 1 1 1 1 1 1 1

예제 출력 2 복사

133

예제 입력 3 복사

5 1 2 3 4 5 5 3 2 4

예제 출력 3 복사

214

예제 입력 4 복사

5 5 5 5 5 5 5 5 5 5

예제 출력 4 복사

130

 

 

2. 소스코드

---

1회차

 

- 윷놀이 판 map을 어떻게 구현할지 고민했던 문제.

- 윷놀이 판 map을 따로 구현하지 않고, 각 핀을 pair (area, position)로 저장하여 풀었음.

- map을 따로 구현하지 않고 로직으로만 푼덕에, 분기점에서 error가 꽃핌.

- 백트래킹을 통해 32ms -> 0ms로 단축.

- 시간복잡도 :  

 말의 중복으로 인한 스킵, 백트래킹 등으로 정확한 시간복잡도 계산이 어려움.

최악의 경우 말의 중복도 없고, 백트래킹도 없는 경우에 O(4^10) 이상

 

 

#pragma warning (disable : 4996)

#include <iostream>
#include <vector>

using namespace std;
int answer;

vector <int> dice;

struct Info
{
    vector<pair<int, int>> pinPlace;

}info;

int calPoint(int area, int pos) {
    if (pos == 21) return 0;
    switch (area)
    {
    case 0: return pos * 2;
    case 1: return 10 + pos * 3;
    case 2: if (pos <= 2) return 20 + pos * 2;
          else return 20 + (pos - 2) * 5;
    case 3: return 29 - pos;
    }
}

void dfs(Info info, int sum, int cnt) {

    if (cnt > 9) {
        if (answer < sum) answer = sum;
        return;
    }
 
    if ((sum + 40 * (10 - cnt)) < answer) // 백트래킹
        return;

    for (int i = 0; i < 4; ++i) {
        //i번 핀을 이동한다.
        // 구역확인
        int area = info.pinPlace[i].first;
        // 위치확인
        int pos = info.pinPlace[i].second;
        //도착말은 PASS
        if (pos == 21) continue;


        //길따라 시작!
         //area 0 지름길 위치라면
        if (area == 0) {
            //10인 경우
            if (pos == 5) {
                //3이하인 경우 지름길 내부
                if (dice[cnt] <= 3) {
                    info.pinPlace[i].first = 1;
                    info.pinPlace[i].second = dice[cnt];
                }
                else {
                    //max : 0 5에서 5가 나오는 경우 2-4 : 끝까지 못감
                    info.pinPlace[i].first = 2;
                    info.pinPlace[i].second = dice[cnt] - 1;
                }
            }
            else if (pos == 10) {
                //max : 0 10에서 5가 나오는 경우 2-5 : 끝까지 못감
                info.pinPlace[i].first = 2;
                info.pinPlace[i].second = dice[cnt];
            }
            else if (pos == 15) {
                //3이하인 경우 지름길 내부
                if (dice[cnt] <= 3) {
                    info.pinPlace[i].first = 3;
                    info.pinPlace[i].second = dice[cnt];
                }
                else {
                    //max : 0 15에서 5가 나오는 경우 2-4 : 끝까지 못감
                    info.pinPlace[i].first = 2;
                    info.pinPlace[i].second = dice[cnt] - 1;
                }
            }
            //area 0 에서 도착점에 도착?
            else if (dice[cnt] + pos >= 21)
            {
                info.pinPlace[i].second = 21;
            }
            //아닌경우 그냥가세요
            else {
                info.pinPlace[i].second = pos + dice[cnt];
            }
        }
        //area 1 이라면
        else if (area == 1) {
            //주사위 + pos가 3칸 넘어가면
            if (dice[cnt] + pos > 3) {
                info.pinPlace[i].first = 2;
                info.pinPlace[i].second = pos + dice[cnt] - 1;
            }
            //max 1-3에서 4,5가 나오는 경우 다른 영역으로간다.
            else info.pinPlace[i].second = pos + dice[cnt];
            if (info.pinPlace[i].second == 6) {
                info.pinPlace[i].first = 0;
                info.pinPlace[i].second = 20;
            }
            else if (info.pinPlace[i].second >= 7) {
                info.pinPlace[i].first = 0;
                info.pinPlace[i].second = 21;
            }
        }
        //area 2 구역에 있다면
        else if (area == 2) {
            //주사위 + pos가 5칸 넘어가면
            if (dice[cnt] + pos == 6) {
                info.pinPlace[i].first = 0;
                info.pinPlace[i].second = 20; //end조건
            }
            else if (dice[cnt] + pos > 6) {
                info.pinPlace[i].first = 0;
                info.pinPlace[i].second = 21; //end조건
            }
            else info.pinPlace[i].second = pos + dice[cnt];
        }
        //area 3 구역에 있다면
        else if (area == 3) {
            //주사위 + pos가 3칸 넘어가면
            if (dice[cnt] + pos > 3) {
                info.pinPlace[i].first = 2;
                info.pinPlace[i].second = pos + dice[cnt] - 1;
            }
            else info.pinPlace[i].second = pos + dice[cnt];
            if (info.pinPlace[i].second == 6) {
                info.pinPlace[i].first = 0;
                info.pinPlace[i].second = 20;
            }
            else if (info.pinPlace[i].second >= 7) {
                info.pinPlace[i].first = 0;
                info.pinPlace[i].second = 21;
            }
        }//말 이동 end

        //중복 체크! 그러나 종료에 있는건 중복체크하면안된다.
        bool check = false;
        for (int k = 0; k < info.pinPlace.size(); ++k) {
            if (i == k) continue;
            if (info.pinPlace[k].first == info.pinPlace[i].first
                and info.pinPlace[k].second == info.pinPlace[i].second
                and info.pinPlace[i].second != 21
                and info.pinPlace[i].second != 0)
                check = true;
        }
        //이미 말이 잉네?
        if (check) {
            //말초기화
            info.pinPlace[i].first = area;
            info.pinPlace[i].second = pos;
            continue;
        }
        int temp = calPoint(info.pinPlace[i].first, info.pinPlace[i].second);
        sum += temp;

        dfs(info, sum, cnt + 1);
        sum -= temp;
        info.pinPlace[i].first = area;
        info.pinPlace[i].second = pos;
    }//for문 end
}

int main() {

    for (int i = 0; i < 4; i++)
        info.pinPlace.push_back({ 0, 0 });

    for (int i = 0; i < 10; ++i) {
        int temp;
        cin >> temp;
        dice.push_back(temp);
    }

    dfs(info, 0, 0);

    cout << answer << '\n';
    return 0;
}