[그래프 / BOJ 17825 / C++] 주사위 윷놀이

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

17825번: 주사위 윷놀이

1) 하나의 숫자로(0, -1, 1) 채워져있는지 확인하고,
1-1) 만약 채워졌다면, 그 숫자를 확인한 후 개수를 세준다.
1-2) 만약 안채워졌다면, 사각형을 9등분한 후 각 사각형마다 다시 1) 과정을 반복한다. 

진짜 말도 안되는 문제..... 아직 초보자인 나에겐 골드의 벽도 어렵다...

 

열심히 해야겠다 ^^.... 자다가도 벌떡 일어나 bfs코드 입력할 수 있는 사람이 되자..

 

일단 문제가 굉장히 복잡하긴 한데, 안의 논리는 간단하다.

 

주어진 input값은 열번의 주사위 값이다. 즉, 뭐가 됐든 말은 무조건 열번 옮기면 끝이라는 말이다.

 

말을 열번 옮기는 경우의 수를 생각해보자.

 

A,B,C,D 말이 있다면, 순서 상관있고, 중복을 허용해서 열번 뽑는다고 말할 수 있다.

 

즉, ABCD 중 하나 뽑을 경우의수를 10제곱하면 된다. = 4의 10승

 

2의 20승 밖에 안되므로 별다른 고민없이 문제의 조건 그대로 따라서 안심하고 구현만 하면된다!!!!!!

 

우선 아래 코드의 setMap 함수를 통해서 윷놀이판을 인접리스트로 만들어주자. 단, 주사위를 굴려서 둬야할 index와

도착한 index 칸의 점수 각각을 저장해야한다!! pair를 사용해도 좋고, 인접리스트와 배열을 둘다 만들어도 괜찮을 것 같다.

 

나는 2,4,6,8,10....40까지 1부터 20의 index를 부여했다. (출발칸은 index = 0 이다. 도착칸 100)

 

이제 go() 함수를 보자.

 

(1) index = 100이면 도착칸

(2) 도착칸이 아니라면, 1번말부터 4번말까지 정해진 주사위수만큼 이동시키는 경우를 모두 구한다.

(3) 주사위수만큼 이동한 칸의 점수를 리턴해준다.

 

이것을 약간 시각화해보자면,

 

이런식으로 4의 10승개의 노드들이 만들어진다!! (그림은 전체 트리의 일부분만을 나타냈다.)

 

go함수는 int를 리턴하므로 우리가 지금까지 풀어왔던 문제들 (효율적인해킹, 트리 등)처럼 말단 노드(10번째 노드)에 도달하고나서

루트노드에 각 말이 도착한 칸의 점수들의 합이 구해질 것이다!!

 

이 논리를 이해하고 나면 이제 다음부터는 코드 구현력 싸움이다.

 

move함수로 bfs를 돌며 주사위 수만큼 말을 이동시킨다.

 

is_Mal이라는 함수를 통해 해당칸에 다른 말이 있어서 사용할 수 없는 말인지 확인하고,

 

최종적으로 해당 칸에 도착해서 얻은 점수의 합을 계산해주고, 리턴해준다!

 

진짜 열심히 자신을 갖고 열심히 풀어보자! (물론 나도 혼자 못풀어서 구글링의 결과다 ..)

 

 

#include <bits/stdc++.h>

using namespace std;

int a[14], v[104], mal[4];
vector<int> adj[60]; // 인접 리스트 생성

void add(int here, int there){
    adj[here].push_back(there);
}

void setMap(){
    
    // 100은 도착 지점.
    
    for(int i = 0 ; i <= 19 ; i++) add(i, i+1); // (0,1) (1,2) (2,3) (3,4)....(19,20) 인접리스트 생성-1
    
    add(5, 21); add(21, 22); add(22, 23); add(23, 24);
    add(15, 29); add(29, 30); add(30, 31); add(31, 24);
    
    add(10, 27); add(27, 28); add(28, 24); add(24, 25);
  
    
    add(25, 26); add(26, 20);
    
    add(20, 100); // 도착. (40 -> 도착)
    
    
    for(int i = 1 ; i <= 20 ; i++) v[i] = 2*i; // 각 index에 해당하는 점수 2~40
    
    v[21] = 13; v[22] = 16; v[23] = 19; v[24] = 25;
    v[27] = 22; v[28] = 24; v[25] = 30; v[26] = 35;
    
    v[29] = 28; v[30] = 27; v[31] = 26;
}

int move(int here, int cnt){
    if(here == 100) return 100; // 도착
    
    if(adj[here].size() >= 2) {here = adj[here][1]; cnt--;}
    // 만약 파란선으로 갈 수 있는 위치 (5(10), 10(20), 15(30), 24(25) 라면 이동)
    // [0]에는 빨간선으로 갈 수 있는 다음것이 저장되있고, [1]에는 파란색으로 갈 수 있는 다음것이 저장됨.
    
    if(cnt){ // 주사위 수만큼 bfs시전
        queue<int> Q;
        Q.push(here);
        int there;
        while(Q.size()){
            int cur = Q.front(); Q.pop();
          
            there = adj[cur][0];
            
            Q.push(there);
            
            if(there==100) break;
            cnt--;
            if(cnt==0) break;
            
        }
        
        return there; // 주사위 수만큼 이동했다면 there 리턴
    } else return here; // 더이상 이동할 수 없다면 here.
    
    
}

bool is_Mal(int mal_idx, int idx){ // mal_idx는 말의 현재 위치, idx는 말의종류
    if(mal_idx==100) return false; // 도착
    for(int i = 0 ; i < 4 ; i++){
        if(i==idx) continue; // 자기 자신이면 무시
        if(mal[i]==mal_idx) return true; // mal_idx가 mal[i]에 있다면 움직일 수 없는 말.
        // 현재 이동 시킨 말 위치(mal_idx)가 다른 말(mal_idx)이 존재한다면 더이상 움직일 수 없는 말을 의미함.
    }
    return false; // 나머지는 false.
}

int go(int here){
    if(here==10) return 0; // 10번째면 종료.
    
    int ret=0;
    
    for(int i = 0 ; i < 4 ; i++){ // 말 4개 선택 중 하나 선택
        int tmp_idx = mal[i]; // 말 1개 선택 (mal의 현재 위치를 저장한다)
        int mal_idx = move(tmp_idx, a[here]); // 해당 주사위 수로 idx 구하기
        if(is_Mal(mal_idx, i)) continue; // 이동시킨 말을 더이상 움직일 수 없으면 continue;
        
        mal[i] = mal_idx; // mal 위치 업데이트
        ret = max(ret, go(here+1) + v[mal_idx]); // 점수의 최대값 구하기 (한개의 말을 고르고 ,, 4개중 다른말 고르고,, 4개중 다른 말 고르고,,, )
        
        mal[i] = tmp_idx; // mal idx 원래대로 돌려주기.
    }
    
    
    return ret; // 결과값 계속 리턴해주기
}




int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    setMap();
    
    
    
    for(int i = 0 ; i < 10 ; i++) cin >> a[i];
    cout << go(0); // 0은 출발지점.
    return 0;
}