BOJ_17825_주사위윷놀이 [DFS by Back Tracking]

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving

---

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

17825번: 주사위 윷놀이

 

 이 문제를 처음 풀기 시작했을 때 한 20분 동안은 멍했다. 분명히 완전 탐색인데 어떻게 '구현'하지? 뭔가 문제가 상당히 난잡해 보였다. 그도 그럴 것이 밑에 제시된 그림만 봐도 현기증 나게 생겼다. 이건 뭐 어쩌라는 거지... 20분은 그렇게 날렸다.

 

 그러다가 실제 시험이라고 생각하니 정신이 들었다. 기존 문제처럼 정갈하게 연결 상태가 주어진 것도 아니고, 친절하게 그림으로 설명을 첨부해 주지도 않았다. 그러면 할 수 있는 것은, 어차피 저 위의 윷놀이 판은 고정되어 있으니 직접 연결하는 수밖에... 바로 다음과 같이 임의로 번호를 매겨 연결해 버렸다. 그리고 그 번호에 해당하는 점수를 저장하는 배열도 만들었다. 

 

직접 번호로 연결함.

 

 일단 이렇게 연결하고 나면 일반적인 back tracking과 동일하다. 조건 문만 적절히 넣어주면 끝난다. 코드에 주석을 달아 놓았으니 코드를 보자. 

 

혹시 이 다른 코드들도 보고 싶으면 

 

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving

kgw4073/Problem-Solving

이것도 보자.

---

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
const int endPoint = 21;
 
// 32개의 노드들을 그래프로 연결
vector<int> graph[33];
 
// score는 32개의 노드들 위에 쓰여있는 점수
int score[33];
 
// state는 해당 인덱스 노드 위에 말이 있는지 없는지
int state[33];
 
// 0 ~ 3번 말이 현재 어느 위치에 있는지
int markerNode[4];
 
// 주사위 결과
int dice[10];
 
// 0 ~ 3번 말들이 끝났는지 안끝났는지
bool finished[4] = { false, };
 
// 답
int answer = 0;
 
void solve(int depth, int total) {
    if (depth == 10) {
        answer = max(answer, total);
        return;
    }
    // 0 ~ 3번 말 탐색
    for (int i = 0; i < 4; i++) {
        // 도착 점에 있는 말이면 탐색 안해
        if (finished[i]) {
            continue;
        }
        int currentNode = markerNode[i];
        int nextNode;
        // 현재 노드가 5, 10, 15이면 파란 선 따라 감
        if (currentNode == 5 || currentNode == 10 || currentNode == 15) {
            int count = dice[depth] - 1;
            nextNode = graph[currentNode][1];
            while (count--) {
                nextNode = graph[nextNode][0];
            }
        }
        else {
            int count = dice[depth];
            nextNode = markerNode[i];
            while (count--) {
                nextNode = graph[nextNode][0];
            }
        }
        // 다음 노드가 끝점이어도 일단 탐색하고 다음 말로 넘어감
        if (nextNode == endPoint) {
            state[currentNode] = 0;
            state[nextNode] = 1;
            markerNode[i] = nextNode;
            finished[i] = true;
            solve(depth + 1, total + score[nextNode]);
            finished[i] = false;
            state[nextNode] = 0;
            state[currentNode] = 1;
            markerNode[i] = currentNode;
            continue;
        }
        // 다음 노드에 뭐 있으면 탐색 안함
        if (state[nextNode]) {
            continue;
        }
        // 다음 노드에 아무 말도 없고 끝점도 아니어도 탐색
        markerNode[i] = nextNode;
        state[currentNode] = 0;
        state[nextNode] = 1;
        solve(depth + 1, total + score[nextNode]);
        state[nextNode] = 0;
        state[currentNode] = 1;
        markerNode[i] = currentNode;
    }
}
int main() {
 
    // 이 밑에 코드는 직접 그래프 번호 매겨서 연결
    for (int i = 0; i <= 20; i++) {
        graph[i].emplace_back(i + 1);
        score[i] = i * 2;
    }
    graph[5].emplace_back(22);
    score[22] = 13;
    graph[22].emplace_back(23);
    score[23] = 16;
    graph[23].emplace_back(24);
    score[24] = 19;
    graph[24].emplace_back(25);
    score[25] = 25;
 
    graph[25].emplace_back(26);
    score[26] = 30;
    graph[26].emplace_back(27);
    score[27] = 35;
    graph[27].emplace_back(20);
 
 
    graph[10].emplace_back(28);
    score[28] = 22;
    graph[28].emplace_back(29);
    score[29] = 24;
    graph[29].emplace_back(25);
 
    graph[15].emplace_back(30);
    score[30] = 28;
    graph[30].emplace_back(31);
    score[31] = 27;
    graph[31].emplace_back(32);
    score[32] = 26;
    graph[32].emplace_back(25);
    graph[21].emplace_back(21);
    for (int i = 0; i < 10; i++) {
        cin >> dice[i];
    }
    solve(0, 0);
    cout << answer;
}