99클럽 코테 스터디 35일차 TIL 구현(주사위 윷놀이)

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

<아이디어>

우선 윷놀이 판을 2차원 배열에 담아주었다.

총 10번의 말 이동 순서를 순열로 뽑은뒤, 해당 순서로 게임을 진행하도록 하였다.

게임을 진행할 때에는 각 말들의 저장해두고 싶은 현 상황을 Point 구조체를 만들어 담아두며 사용했다.

이때 가장 중요한 것은 25, 30, 35, 40에서의 방문 처리 였는데, 이미 말이 놓여있는 자리로 이동하는 말의 경우 사용하면 안된다는 조건이 까다로웠다.

결과 적으로 아래와 같이 제출하였지만 조금 더 다듬어야 할 것 같다.

 

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

public class Main {

    static class Point{
        int dir;
        int idx;
        int sum;
        boolean out;
        Point(int dir, int idx, int sum, boolean out){
            this.dir = dir;
            this.idx = idx;
            this.sum = sum;
            this.out = out;
        }
    }

    static int[][] score = {
            {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40},
            {10, 13, 16, 19, 25, 30, 35, 40},
            {20, 22, 24, 25, 30, 35, 40},
            {30, 28, 27, 26, 25, 30, 35, 40}
    };
    static boolean[] visit1 = new boolean[20];
    static int[] arr;
    static Point[] dice;
    static int ans;

    public static boolean isVisit(int num, int dir, int idx) {
        if (idx >= score[dir].length) return true;
        for (int i = 0; i < 4; i++) {
            if (i == num || dice[i].out) continue;
            if (dice[i].dir == dir && dice[i].idx == idx) return false;
            if (score[dir][idx] == score[dice[i].dir][dice[i].idx] &&
                    (score[dir][idx] == 25 || score[dir][idx] == 30 || score[dir][idx] == 35 || score[dir][idx] == 40)) {
                return false;
            }
        }
        return true;
    }



    public static void playDice(int[] input) {
        dice = new Point[4];
        for (int i = 0; i < 4; i++) {
            dice[i] = new Point(0, 0, 0, false);
        }

        for (int i = 0; i < 10; i++) {
            int d = input[i];
            if (dice[d].out) return;

            int n = arr[i];
            int curDir = dice[d].dir, curIdx = dice[d].idx;
            int nextIdx = curIdx + n;

            // 파란칸 이동
            if (curDir == 0 && curIdx == 5) {
                curDir = 1; nextIdx = n;
            } else if (curDir == 0 && curIdx == 10) {
                curDir = 2; nextIdx = n;
            } else if (curDir == 0 && curIdx == 15) {
                curDir = 3; nextIdx = n;
            }

            if (nextIdx >= score[curDir].length) {
                dice[d].out = true;
                continue;
            }

            if (!isVisit(d, curDir, nextIdx)) return;
            dice[d] = new Point(curDir, nextIdx, dice[d].sum + score[curDir][nextIdx], false);
        }

        int tmp = 0;
        for (int i = 0; i < 4; i++) {
            tmp += dice[i].sum;
        }
        ans = Math.max(ans, tmp);
    }



    public static void permu(int cnt, int[] input){
        if(cnt == 10) {
            playDice(input);
            return;
        }
        for(int i=0; i<4; i++){
            input[cnt] = i;
            permu(cnt+1, input);
        }
    }

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

        arr = new int[10];
        for(int i=0; i<10; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] input = new int[10];
        permu(0, input);

        System.out.println(ans);
    }
}