[백준 17825번] 주사위 윷놀이

문제 링크: 17825번 주사위 윷놀이

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

 

채점 현황을 보니 최적화된 코드에 비해 시간은 2배, 메모리는 5배 정도 더 잡아먹는 것 같다. 많은 개선이 필요해 보인다.

 

move(): 하나의 horse 배열이 완성되었을 때, 점수를 구한다.

board: board[i][j] = k이면 '출발지에서 도착지로 가는 4개의 경로 중 i번째 경로'의 'j 위치'에 '쓰인 숫자'는 k이다.

horse: horse[i] = k이면 'i번째 주사위'에는 '말 k'를 움직인다.

pos[i] = k이면 '말 i'의 위치는 k이다.

score[i] = k이면 '말 i'의 점수는 k이다.

path[i] = k이면 '말 i'는 '출발지에서 도착지로 가는 4개의 경로 중 k번째 경로'를 이용 중이다.

 

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

public class Main {
    static int[] dice; // 주사위 숫자
    static int[] horse = new int[10]; // horse[i]=k: i턴은 k말이 움직인다.
    static int[][] board = new int[4][];
    static int answer = 0;

    static int sum(int[] arr) {
        int sum = 0;
        for (int i : arr)
            sum += i;
        return sum;
    }

    static int move() {
        int[] pos = new int[4]; // 도착했을 땐 -1
        int[] score = new int[4];
        int[] path = new int[4];

        for (int t = 0; t < 10; t++) {
            int curDice = dice[t];
            int curHorse = horse[t];

            // 이미 도착한 말을 움직이려고 하면...
            if (pos[curHorse] == -1)
                return 0; // 이 조합은 잘못된 턴 조합임

            // 5, 10, 15번 칸에서는 분기
            if (path[curHorse] == 0) {
                switch (pos[curHorse]) {
                    case 5: path[curHorse] = 1; break;
                    case 10: path[curHorse] = 2; break;
                    case 15: path[curHorse] = 3; break;
                    default: break;
                }
            }

            ////////// 말 이동 //////////
            pos[curHorse] += curDice;

            // 도착했다면...
            if (pos[curHorse] >= board[path[curHorse]].length) {
                pos[curHorse] = -1;
                continue;
            }

            // 이동을 마치는 칸에 다른 말이 있으면...
            for (int i = 0; i < 4; i++) {
                if (i == curHorse) continue;

                int pos1 = pos[curHorse];
                int pos2 = pos[i];
                int path1 = path[curHorse];
                int path2 = path[i];

                // i말이 도착한 상태이면
                if (pos2 == -1) continue;

                /* 여기서부터는 모두 잘못된 조합임 */
                // 1. 동일 path일 때 동일 칸
                if (path1 == path2 && pos1 == pos2)
                    return 0;

                // 2. 다른 path일 때 동일 칸
                int board1 = board[path1][pos1];
                int board2 = board[path2][pos2];

                if ((board1 == 10 && board2 == 10) ||
                        (board1 == 20 && board2 == 20) ||
                        (board1 == 40 && board2 == 40) ||
                        (board1 == 25 && board2 == 25))
                    return 0;

                // 3. 30의 경우
                if ( (pos1==15&&pos2==15) && ((path1==0&&path2==3)||(path1==3&&path2==0)) ) return 0;

                if ( ((path1==1&&pos1==10)&&(path2==2&&pos2==14)) || ((path1==2&&pos1==14)&&(path2==1&&pos2==10)) ||
                        ((path1==1&&pos1==10)&&(path2==3&&pos2==20)) || ((path1==3&&pos1==20)&&(path2==1&&pos2==10)) ||
                        ((path1==2&&pos1==14)&&(path2==3&&pos2==20)) || ((path1==3&&pos1==20)&&(path2==2&&pos2==14)) )
                    return 0;

                // 4. 35의 경우
                if (board1==35 && board2==35) return 0;
            }

            ////////// 점수 추가 //////////
            if (pos[curHorse] != -1)
                score[curHorse] += board[path[curHorse]][pos[curHorse]];
        }

        return sum(score);
    }

    static void setMaxScore(int idx) {
        if (idx == 10) {
            int res = move();
            if (res > answer)
                answer = res;
            return;
        }

        for (int i = 0; i < 4; i++) {
            horse[idx] = i;
            setMaxScore(idx + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dice = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        board[0] = new int[21];
        for (int i = 0; i < 21; i++)
            board[0][i] = i*2;
        board[1] = new int[]{0, 2, 4, 6, 8, 10, 13, 16, 19, 25, 30, 35, 40};
        board[2] = new int[]{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 25, 30, 35, 40};
        board[3] = new int[]{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 28, 27, 26, 25, 30, 35, 40};

        setMaxScore(0);

        System.out.println(answer);
    }
}