[TIL] 99클럽 코테 스터디 35일차 TIL + 백준 17825 주사위 윷놀이

 

문제 풀이

 

문제 풀이

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static StringTokenizer st;
    static int N;
    static int answer;
    static int[] Dice = new int[10+1]; 
    static int[] Order = new int[10+1]; 
    static ArrayList<Integer> OrderArr = new ArrayList<>();
    static Node root = new Node();

    static Node[] Mal = new Node[4+1]; 

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        for(int i=1;i<11;i++){
            Dice[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.fill(Mal,root);

        initMap();
        permutation(1);
        System.out.println(answer);
    }

    static void permutation(int count){
        if(count>=11){
            Arrays.fill(Mal,root); 
            answer = Math.max(answer,gameStart());
            for(int i=1;i<5;i++){ 
                Mal[i].isHere = false;
            }
            return;
        }
        for(int i=1;i<5;i++){ 
            Order[count] = i; 
            permutation(count+1);
        }
    }

    static int gameStart(){
        int score = 0;
        boolean[] Goal = new boolean[5];

        for(int t=1;t<11;t++){
            int dice = Dice[t]; //1~5
            int nowMalIndex = Order[t]; //1~4
            Node nowMal = Mal[nowMalIndex]; 

            nowMal.isHere = false; 

            if(Goal[nowMalIndex]){
                return 0;
            }
            for(int i=0;i<dice;i++){ 
                if(i==0 && nowMal.isBlue){ 
                    nowMal = nowMal.getChild(true);
                }
                else{
                    nowMal  = nowMal.getChild(false);
                }

                if(nowMal.isEnd){ 
                    Goal[nowMalIndex] = true;
                    break;
                }
                if(i==dice-1){ 
                    if(!nowMal.isHere) { 
                        score += nowMal.value;
                        nowMal.isHere = true;
                        Mal[nowMalIndex] = nowMal;
                    }
                    else{
                        return 0;
                    }
                }
            }
        }
        return score;
    }

    static void initMap(){
        Node now = root;
        //40 -> 도착
        Node last40 = new Node(40);
        last40.child = new Node(0);
        last40.child.isEnd = true;

        //25 -> 30 -> 35 -> 40
        Node middle25 = new Node(25);
        Node tmp = middle25.child = new Node(30);
        tmp = tmp.child = new Node(35);
        tmp.child = last40;

        //2,4,6,8,10,13,16,19,25
        now = now.child = new Node(2);
        now = now.child = new Node(4);
        now = now.child = new Node(6);
        now = now.child = new Node(8);
        now = now.child = new Node(10);
        now.isBlue = true;

        tmp = now.blueChild = new Node(13);
        tmp = tmp.child = new Node(16);
        tmp = tmp.child = new Node(19);
        tmp.child = middle25;

        now = now.child = new Node(12);
        now = now.child = new Node(14);
        now = now.child = new Node(16);
        now = now.child = new Node(18);
        now = now.child = new Node(20);
        now.isBlue = true;

        tmp = now.blueChild = new Node(22);
        tmp = tmp.child = new Node(24);
        tmp.child = middle25;

        now = now.child = new Node(22);
        now = now.child = new Node(24);
        now = now.child = new Node(26);
        now = now.child = new Node(28);
        now = now.child = new Node(30);
        now.isBlue = true;

        tmp = now.blueChild = new Node(28);
        tmp = tmp.child = new Node(27);
        tmp = tmp.child = new Node(26);
        tmp.child = middle25;

        now = now.child = new Node(32);
        now = now.child = new Node(34);
        now = now.child = new Node(36);
        now = now.child = new Node(38);
        now.child = last40;
    }

    static class Node{
        int value; 
        boolean isEnd; 
        boolean isBlue; 
        boolean isHere; 
        Node child;
        Node blueChild;

        public Node(int value) {
            this.value = value;
        }

        public Node() {
        }

        Node getChild(boolean imBlue){
            if(!imBlue)
                return child; 
            else
                return blueChild; 
        }
    }
}