[백준 17825번] 주사위 윷놀이 (C++)

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

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

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

---

10,20,30에서 출발할 때 파란색길로 가는걸 처리하는 문제다.

이 문제는 2차원 배열, 1차원 배열과 같은 탐색이 아니라 특정 게임판을 탐색한다.

따라서 게임판을 방향 그래프로 보고 도착할 수 있는 지점들의 관계를 표현해줘야 한다.

이 전처리 과정을 본인이 구현하고자 하는 알고리즘에 맞게 잘 설정하고 시작해야 한다.

 

방향성 그래프이므로 노드 구조체에 값과 다음 노드를 설정해놓았다.

그리고 현재 노드의 위치가 

if((cur < 5) || (cur > 5 && cur < 10) || (cur > 10 && cur < 15))

를 만족할 경우는 노드 하나하나 방문할 필요 없이 주사위 값만큼 바로 전진시킨다.

 

이동할 곳에 말이 이미 있으면 이동을 못하는 것까지 확인하고 탐색한다.

 

#include <iostream>
using namespace std;

struct Node {
  int value, next;
};

int dice[10], pos[4], visited[33], point, ans = -1;
Node node[33];

void setGraph(){
  //빨간색 정방향
  for(int i = 0; i < 21; i++){
    node[i].value = i*2;
    node[i].next = i+1;
  }
  //파란색 방향 설정
  node[5].next = 22;
  node[10].next = 25;
  node[15].next = 27;
  //10road
  node[22].next = 23;
  node[23].next = 24;
  node[24].next = 30;
  node[22].value = 13;
  node[23].value = 16;
  node[24].value = 19;
  //20road
  node[25].next = 26;
  node[26].next = 30;
  node[25].value = 22;
  node[26].value = 24;
  //30road
  node[27].next = 28;
  node[28].next = 29;
  node[29].next = 30;
  node[27].value = 28;
  node[28].value = 27;
  node[29].value = 26;
  //final
  node[30].next = 31;
  node[31].next = 32;
  node[32].next = 20;
  node[30].value = 25;
  node[31].value = 30;
  node[32].value = 35;

  node[21].value = 0;
  node[21].next = -1;
}

bool checkPos(int cur, int cnt){
  int tmpNode;
  if((cur < 5) || (cur > 5 && cur < 10) || (cur > 10 && cur < 15)){
    tmpNode = cur + cnt;
  }
  else{
    tmpNode = cur;
    for(int i = 0; i < cnt; i++){
      tmpNode = node[tmpNode].next;
      if(tmpNode == 21) return true;
    }
  }

  for(int i = 0; i < 4; i++){
    if(pos[i] == tmpNode) return false;
  }
  return true;
}

void trial(int step){
  if(step==10){
    ans = max(ans,point);
    return;
  }

  for(int i = 0; i < 4; i++){
    int savePos = pos[i];
    int nNode = pos[i];
    if(pos[i] != 21 && checkPos(nNode,dice[step])){
      if((pos[i] < 5) || (pos[i] > 5 && pos[i] < 10) || (pos[i] > 10 && pos[i] < 15)){
        nNode = pos[i] + dice[step];
      }
      else{
        for(int j = 0; j < dice[step]; j++){
          nNode = node[nNode].next;
          if(nNode == 21) break;
        }
      }
      pos[i] = nNode;
      point += node[nNode].value;
      trial(step+1);
      pos[i] = savePos;
      point -= node[nNode].value;
    }
  }
}

int main(){
  for(auto &i:dice) cin >> i;
  setGraph();
  trial(0);
  cout << ans;
}