[BaekJoon] 17825 주사위 윷놀이 (Java)

1.  문제 링크

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

2.  문제

요약

• 주사위 윷놀이는 위와 같은 게임판에서 하는 게임입니다.
  • 처음에는 시작 칸에 말 4개가 있습니다.
  • 말은 게임판에 그려진 화살표 방향대로만 이동할 수 있습니다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 합니다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계없이 이동을 마칩니다.
  • 게임은 10개의 턴으로 이루어집니다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킵니다.
  • 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없습니다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있습니다.
  • 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가됩니다.
• 주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 주사위에서 나올 수 10개가 순서대로 주어집니다.
• 출력: 첫 번째 줄에 얻을 수 있는 점수의 최댓값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

class Space {
    int score;
    boolean isEmpty, isFinish;
    Space next;
    Space shortcut;
    public Space(int score) {
        this.score = score;
        this.isEmpty = true;
    }

    public Space add(int score) {
        Space next = new Space(score);
        this.next = next;
        return next;
    }

    public static Space getSpace(Space start, int score) {
        Space temp = start;
        while(true) {
            if(temp == null) return null;
            if(temp.score == score) return temp;
            temp = temp.next;
        }
    }
}

public class Main {
    static final int SIZE = 10, HSIZE = 4;
    static int[] dices, horsePerDice;
    static Space[] horses;
    static Space start;
    static int answer;
    static void input() {
        Reader scanner = new Reader();
        dices = new int[SIZE + 1];
        horsePerDice = new int[SIZE + 1];
        horses = new Space[HSIZE + 1];
        for(int idx = 1; idx <= SIZE; idx++) dices[idx] = scanner.nextInt();
    }

    static void solution() {
        makeMap();
        decideOrder(1);
        System.out.println(answer);
    }

    static void decideOrder(int index) {
        if(index > SIZE) {
            answer = Math.max(answer, game());
            return;
        }
        for(int idx = 1; idx <= HSIZE; idx++) {
            horsePerDice[index] = idx;
            decideOrder(index + 1);
        }
    }

    static int game() {
        Arrays.fill(horses, start); // 모든 말 시작 지점에 두기

        int score = 0;
        for(int idx = 1; idx <= SIZE; idx++) {
            Space cur = horses[horsePerDice[idx]];
            cur.isEmpty = true; // 말을 이동시킬 것이기 때문에 현재 위치를 비도록 함

            for(int move = 1; move <= dices[idx]; move++) {
                if(move == 1 && cur.shortcut != null) {
                    // 현재 말이 지름길이 있는 곳에 위치한 경우 지름길로 이동
                    cur = cur.shortcut;
                } else {
                    cur = cur.next;
                }
            }

            horses[horsePerDice[idx]] = cur;

            if(!cur.isEmpty && !cur.isFinish) {
                // 끝나는 지점이 아닌 곳에서 말이 놓여져 있는 경우
                // 이 순서로 말을 배치할 경우는 불가함
                score = 0;
                break;
            } else {
                cur.isEmpty = false;
                score += cur.score;
            }
        }

        for(int horse = 1; horse <= HSIZE; horse++) {
            horses[horse].isEmpty = true;
        }

        return score;
    }

    static void makeMap() {
        // 시작 지점
        start = new Space(0);

        // 지름길을 제외한 길
        Space temp = start;
        for(int score = 2; score <= 40; score += 2) temp = temp.add(score);

        // 도착 지점
        Space end = temp.add(0);
        end.isFinish = true;
        end.next = end; // 도착 지점을 넘어설 때를 대비해 NullPointerException이 나지 않도록

        // 지름길의 중앙 부분
        Space center = new Space(25);

        // 중앙 부분부터 도착 지점까지
        temp = center.add(30);
        temp = temp.add(35);
        temp.next = Space.getSpace(start, 40);

        // 10점부터 중앙 부분까지 지름길
        temp = Space.getSpace(start, 10);
        temp = temp.shortcut = new Space(13);
        temp = temp.add(16);
        temp = temp.add(19);
        temp.next = center;

        // 20점부터 중앙 부분까지 지름길
        temp = Space.getSpace(start, 20);
        temp = temp.shortcut = new Space(22);
        temp = temp.add(24);
        temp.next = center;

        // 30점부터 중앙 부분까지 지름길
        temp = Space.getSpace(start, 30);
        temp = temp.shortcut = new Space(28);
        temp = temp.add(27);
        temp = temp.add(26);
        temp.next = center;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}