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

문제

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

---

풀이(40분)

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

public class Main {

    static final int[] MAP = {
            0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
            22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0,
            10, 13, 16, 19, 25, 30, 35, 40, 0,
            20, 22, 24, 25, 30, 35, 40, 0,
            30, 28, 27, 26, 25, 30, 35, 40, 0
    };

    static final int[] FINISH_POINTS = {21, 30, 38, 47};
    static final int[] dice = new int[10];
    static final int[] pieceMoves = new int[10];
    static int maxScore = 0;

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

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

        generateMoves(0);
        System.out.println(maxScore);
    }

    static void generateMoves(int depth) {
        if (depth == 10) {
            simulateGame();
            return;
        }

        for (int i = 0; i < 4; i++) {
            pieceMoves[depth] = i;
            generateMoves(depth + 1);
        }
    }

    static void simulateGame() {
        int[] piecePositions = new int[4];
        boolean[] visited = new boolean[MAP.length];
        int score = 0;

        for (int i = 0; i < 10; i++) {
            int piece = pieceMoves[i];
            int diceValue = dice[i];

            if (isFinished(piecePositions[piece])) return;

            int next = getNextPosition(piecePositions[piece], diceValue);
            if (isFinished(next)) {
                updateVisited(visited, piecePositions[piece], false);
                piecePositions[piece] = next;
                continue;
            }

            if (isVisited(visited, next)) return;

            updateVisited(visited, piecePositions[piece], false);
            updateVisited(visited, next, true);

            piecePositions[piece] = next;
            score += MAP[next];
        }

        maxScore = Math.max(maxScore, score);
    }

    static int getNextPosition(int current, int dice) {
        int next = current + dice;

        if (current < 21) {
            if (next >= 21) return 21;
        } else if (current < 30) {
            if (next >= 30) return 30;
        } else if (current < 38) {
            if (next >= 38) return 38;
        } else {
            if (next >= 47) return 47;
        }

        if (next == 5) return 22;
        if (next == 10) return 31;
        if (next == 15) return 39;

        return next;
    }

    static boolean isFinished(int idx) {
        for (int fin : FINISH_POINTS) {
            if (idx == fin) return true;
        }
        return false;
    }

    static boolean isVisited(boolean[] visited, int idx) {
        int groupKey = getGroupKey(idx);
        return visited[groupKey];
    }

    static void updateVisited(boolean[] visited, int idx, boolean value) {
        int groupKey = getGroupKey(idx);
        visited[groupKey] = value;
    }

    static int getGroupKey(int idx) {
        // 점수가 같은 위치들은 동일 그룹으로 처리
        if (idx == 20 || idx == 29 || idx == 37 || idx == 46) return 20;
        if (idx == 26 || idx == 34 || idx == 43) return 26;
        if (idx == 27 || idx == 35 || idx == 44) return 27;
        if (idx == 28 || idx == 36 || idx == 45) return 28;
        return idx;
    }
}

---

문제 풀이 전략

 

사실 하나의 주사위 결과에 4개의 주사위 움직임에 대해 선택을 해줘야 했기에 4^10이라고 생각했다.

그렇다면? 시간 복잡도 상에는 하나도 문제가 없다.

 

하지만 구현이 너무 복잡했고, 맵을 직접 만들어 매번 결정을 해주는 수밖에 없었다.