[Day35]JAVA 백준 주사위 윷놀이(17825번)

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

 

🌕 최종코드

import java.io.*;
import java.util.*;

public class Main {

    private static final int N = 10;
    private static final int M = 4;
    private static final int START = 0;
    private static final int END = 42;

    private static final int[] moves = new int[N];
    private static final List<List<Node>> graph = new ArrayList<>();

    private static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            moves[i] = Integer.parseInt(stz.nextToken());
        }

        makeGraph();

        int[] order = new int[N];
        makeOrder(order, 0); // 중복 순열

        System.out.println(max);

        br.close();
    }

    // 게임 판 생성
    private static void makeGraph() {
        graph.add(new ArrayList<>()); // 0
        graph.add(new ArrayList<>()); // 1

        // 빨간색길 먼저 생성
        graph.get(START).add(new Node(START, START, START + 2, false));
        for (int i = START + 2; i <= END; i++) {
            graph.add(new ArrayList<>());

            if (i % 2 == 0) {
                graph.get(i).add(new Node(i - 2, i, i + 2, false));
            }
        }

        // 지름길 생성
        // 10 ~ 25
        graph.get(10).add(new Node(8, 10, 13, true));
        for (int i = 13; i <= 16; i += 3) {
            graph.get(i).add(new Node(i - 3, i, i + 3, true));
        }
        graph.get(19).add(new Node(16, 19, 25, true));

        // 20 ~ 25
        for (int i = 20; i <= 22; i += 2) {
            graph.get(i).add(new Node(i - 2, i, i + 2, true));
        }
        graph.get(24).add(new Node(22, 24, 25, true));

        // 30 ~ 25
        graph.get(30).add(new Node(28, 30, 28, true));
        for (int i = 27; i >= 26; i--) {
            graph.get(i).add(new Node(i + 1, i, i - 1, true));
        }
        graph.get(28).add(new Node(30, 28, 27, true));

        // 25 ~ 40
        // 25로 가는 경우는 19, 24, 26이 있지만 결국 25에서 한 쪽 방으로만 움직이므로 -1로 함
        graph.get(25).add(new Node(-1, 25, 30, true));
        for (int i = 30; i <= 35; i += 5) {
            graph.get(i).add(new Node(i - 5, i, i + 5, true));
        }
    }

    // 중복 순열 생성
    private static void makeOrder(int[] order, int depth) {
        if (depth == N) {
            max = Math.max(max, moving(order));
            return;
        }

        for (int i = 0; i < M; i++) {
            order[depth] = i;
            makeOrder(order, depth + 1);
        }
    }

    // 만들어진 순열에 맞춰 윷놀이 이동
    private static int moving(int[] order) {
        int total = 0;
        Node[] locations = new Node[M];
        for (int i = 0; i < M; i++) {
            locations[i] = new Node(START, START, START + 2, false);
        }

        Loop1: for (int t = 0; t < N; t++) {
            int mal = order[t];
            int power = moves[t];

            Node currentNode = locations[mal];

            // 도착지점에 있는 것을 움직이려고 할 경우 -> 불가능함(만들어진 순열에 따라서만 움직여야 됨)
            if(currentNode.from == END){
                total = 0;
                break;
            }

            // 주사위 결과에 따른 이동지점
            Node nextNode = nextLocation(currentNode, power);

            // 이미 다른 말판이 이동하고자 하는 자리에 있을 경우
            for (int i = 0; i < 4; i++) {
                // 문제 조건에 의해 이동지점이 도착인 경우 가능
                if(locations[i].from == END) continue;

                // 이동을 마치는 칸에 다른 말이 있으면
                if ((locations[i].isEqualNode(nextNode))) {
                    total = 0;
                    break Loop1;
                }
            }

            locations[mal] = nextNode;
            total += nextNode.from;

            if(nextNode.from == END) total -= END;
        }

        return total;
    }

    private static Node nextLocation(Node currenNode, int power) {
        Node cn = currenNode;

        while (power-- > 0) {
            if (cn.from == END) break;

            if (graph.get(cn.to).size() == 2) {
                cn = (!cn.isShortCut) ? graph.get(cn.to).get(0) : graph.get(cn.to).get(1);

            } else if (graph.get(cn.to).size() == 1) {
                cn = graph.get(cn.to).get(0);
            } else {
                // 30일 때
                if (!cn.isShortCut) {
                    cn = graph.get(cn.to).get(0);
                } else {
                    if (cn.before == -1) {
                        cn = graph.get(cn.to).get(2); // 25 -> 30 일 경우
                    } else {
                        cn = graph.get(cn.to).get(1); // 28 -> 30 일 경우
                    }
                }
            }
        }

        if (cn.from == 10) {
            cn = graph.get(10).get(1);
        } else if (cn.from == 20) {
            cn = graph.get(20).get(1);
        } else if (cn.from == 30) {
            if(cn.to != 35) {
                cn = graph.get(30).get(1);
            }
        }

        return cn;
    }

    private static class Node {
        int before; // 뒷 번호
        int from; // 현재 번호
        int to; // 앞 번호
        boolean isShortCut; // 지름길

        Node(int before, int from, int to, boolean isShortcut) {
            this.before = before;
            this.from = from;
            this.to = to;
            this.isShortCut = isShortcut;
        }


        public boolean isEqualNode(Node node) {
            if(this.before != node.before || this.from != node.from ||
                    this.to != node.to || this.isShortCut != node.isShortCut) {
                return false;
            }
            return true;
        }
    }
}