1. 문제 설명 📌

2. 구현 방법 🗃️

KEY WORD: SIMUlATION, BRUTE FORCE

0️⃣ 윷놀이판 구현, 말의 위치 나타낼 배열 구현
1️⃣ 10번의 주사위 각각으로 움직일 말을 중복순열로 구한다. ($4^{10}$)
2️⃣ 이제 주사위 하나당 움직일 말이 무엇인지 순서도 정했음으로, 그대로 말을 움직여 본다.
- 2️⃣-1) 현재 움직일 말의 시작 노드에 파란색 화살표가 있을 경우, 그것이 가리키는 곳으로 이동
- 2️⃣-2) 윷놀이 판의 최종 위치가 아닌데도, 말이 도착한 위치에 다른 말이 이미 존재한다면 이번 순서는 의미가 없으므로, 1️⃣로 회귀
- 2️⃣-3) 1️⃣번에서 구한 모든 말의 순서에 대하여 2️⃣을 진행한다.
3️⃣ 지금까지 진행한 순서 중 누적 점수 값의 최대값을 구한다.

(1) 필자가 윷놀이판을 입력으로 넣은 방법

총 배열 33개에 값을 차례대로 넣었는데, 주황 ➜ 파랑 ➜ 분홍 ➜ 녹색 순서로 넣었다.

 private static class Node {
        int score;
        int blue;
        int red;

        public Node (int score, int blue, int red){
            this.score = score;
            this.blue = blue;
            this.red = red;
        }
    }

윷놀이의 노드를 나타내는 Class Node는 모두 파란색 화살표가 가리키는 목적지, 빨간색 화살표가 가리키는 목적지를 가지고 있고, 파란색 화살표가 없는 경우, -1을 저장했다.

(2) 시간복잡도 분석 🕓

윷놀이 판의 Node 수: 33개, 말의 수: 4, 움직임: 10번

중복 순열은 10개의 칸이 4개 중 하나를 선택하는 것이었음으로, $4^{10} = 1048576$ 개의 순서가 존재한다.
하나의 순서 당, 10개의 움직임이 있고, 하나의 움직임 당 갈 수 있는 최대 거리는 5임. $50$

총 $52,428,800$ 번의 연산이 필요. 이는 $10^{7}$에서 $10^{8}$ 사이임으로 SAFE

3. 코드 소개 🔎

(1) SUDO CODE

0️⃣ init(): 윷놀이 판을 입력으로 주지 않기 떄문에 전부 받아야함 ㄷㄷ. (이게 빡침)
```
  `dice_num []`: 던져서 나온 주사위 데이터 받기
```
1️⃣ set Order(): 중복 순열을 활용해 10번의 주사위 결과가 각각 어떤 윷놀이 말의 것인지 순서 정하기
2️⃣ 이제 10번의 주사위 각각 던진 사람이 누구인지 정해졌음 따라서 이제 10번의 주사위 결과에 맞게 말을 옮긴다.
- 2️⃣-0) horse_loc []: 이번 순서에 맞게 이동했을 때, 말들의 위치,
```
    `is exist []`: index = 노드 번호, value = 그곳에 말이 있는가?
    `now_horse_num`: 움직일 말의 번호
    `now_moving_cnt`: 현재 사용할 주사위 결과(말을 움직일 횟수)
    `now_horse_location`: 이번에 움직일 말의 현 위치
```
- 2️⃣-1) 주사위 결과에 맞게 말을 움직인다. (만약 처음에 말이 서있는 위치가 파란 화살표가 있는 곳이라면, 파란 화살표 쪽으로 간다.)
- 2️⃣-2) 이동을 마치고 서 있는 곳에 이미 다른 말이 있다면 -1 return하고 그대로 2️⃣ 종료하고 다시 1️⃣수행
- 2️⃣-3) 지금의 이동이 유효하다면, 2️⃣-0)의 변수들 모두 현재 위치한 곳으로 최신화 + 점수 더하기
3️⃣ 지금까지 수행한 2️⃣의 답 중 최대값을 출력한다.

(2) JAVA CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Main {

    private static class Node {
        int score;
        int blue;
        int red;

        public Node (int score, int blue, int red){
            this.score = score;
            this.blue = blue;
            this.red = red;
        }
    }
    static int ans = 0;
    static Node [] nodes = new Node[33];
    static int [] horse_loc;                                     // 현재 각 말들의 위치
    static boolean [] is_exist;                                  // 해당 노드 번호에 말이 존재하는지
    static int [] dice_num = new int [10];                      // 10개의 주사위 넘버
    static int [] horse_order = new int [10];                   // 각 10개의 주사위 당 움직일 말 번호
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        for (int i = 0; i < 10; i++) {
            dice_num[i] = Integer.parseInt(st.nextToken());
        }
        init();
        set_order(10, 0);
        System.out.println(ans);
    }

    public static void set_order(int n, int k){
        if(n == k) {
            ans = Math.max(ans, move());
            return;
        }

        for (int i = 0; i < 4; i++) {
            horse_order[k] = i;
            set_order(n, k+1);
        }
    }

    public static int move(){
        int sum_score = 0;
        horse_loc = new int [4];
        is_exist = new boolean[33];
        for (int i = 0; i < 10; i++) {
            int now_horse_num = horse_order[i];
            int now_moving_cnt = dice_num[i];
            int now_horse_location = horse_loc[now_horse_num];
            is_exist[now_horse_location] = false;
            for (int j = 0; j < now_moving_cnt; j++) {
                if(j == 0 && nodes[now_horse_location].blue != -1){
                    now_horse_location = nodes[now_horse_location].blue;
                }else{
                    now_horse_location = nodes[now_horse_location].red;
                }
            }
            if(now_horse_location < 32 && is_exist[now_horse_location]) return -1; // 이미 그 위치에 누군가 있다면, 이번 주기는 안되는 주기 따라서 그냥 탈출
            horse_loc[now_horse_num] = now_horse_location;
            is_exist[now_horse_location] = true;
            sum_score += nodes[now_horse_location].score;
        }
        return sum_score;
    }

    public static void init(){
        for (int i = 0; i <= 20; i++) {
            nodes[i] = new Node(i*2, -1, i+1);
        }
        // 중앙 십자가 표현
        nodes[21] = new Node(13,-1,22);
        nodes[22] = new Node(16,-1,23);
        nodes[23] = new Node(19,-1,24);
        nodes[24] = new Node(25,-1,30); // 중앙 노드
        nodes[25] = new Node(26,-1,24);
        nodes[26] = new Node(27,-1,25);
        nodes[27] = new Node(28,-1,26);
        nodes[28] = new Node(22,-1,29);
        nodes[29] = new Node(24,-1,24);
        nodes[30] = new Node(30,-1,31);
        nodes[31] = new Node(35,-1,20);
        // 파란색 길 추가
        nodes[5].blue = 21;
        nodes[10].blue = 28;
        nodes[15].blue = 27;
        // 도착 노드 추가 및 도착 전 노드 red 수정
        nodes[32] = new Node(0, -1,32);
        nodes[20].red = 32;
    }
}