이번에 풀어본 문제는
백준 17825번 주사위 윷놀이 입니다.

📕 문제 링크

❗️코드

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

class Piece2
{
    int loc;
    boolean isDone;
    boolean onShortcut;

    public Piece2(int loc)
    {
        this.loc = loc;
    }
}
public class Main {
    static int max_val = Integer.MIN_VALUE;
    static int [] dice;
    static Piece2 [] piece;
    static int [] shortcut;
    static int [] perm;
    static boolean [][] visited;
    static boolean isValid;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        dice = new int[10];
        piece = new Piece2[4];
        shortcut = new int[42];

        // 지름길
        shortcut[10] = 13;
        shortcut[13] = 16;
        shortcut[16] = 19;
        shortcut[19] = 25;
        shortcut[20] = 22;
        shortcut[22] = 24;
        shortcut[24] = 25;
        shortcut[25] = 31;
        shortcut[30] = 28;
        shortcut[31] = 35;
        shortcut[35] = 40;
        shortcut[28] = 27;
        shortcut[27] = 26;
        shortcut[26] = 25;
        shortcut[40] = 41;


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

        perm = new int[10];
        perm(0);
        System.out.print(max_val);
    }
    static void perm(int depth)
    {
        if(depth > 9)
        {
            max_val = Math.max(max_val,play());
            return;
        }

        for(int i = 0; i < 4; ++i)
        {
            perm[depth] = i;
            perm(depth+1);
        }
    }
    static int play()
    {
        int total = 0;
        visited = new boolean[2][42];
        isValid = true;
        for(int i = 0; i < 4; ++i) piece[i] = new Piece2(0);

        for(int i = 0; i < 10; ++i)
        {
            total += move(perm[i],dice[i]);
            if(!isValid) return 0;
        }

        return total;
    }
    static int move(int num,int val)
    {
        if(piece[num].isDone) return 0;
        int map = piece[num].onShortcut ? 1 : 0;
        visited[map][piece[num].loc] = false;

        if(map > 0) // 지름길
        {
            for(int i = 0; i < val; ++i)
            {
                piece[num].loc = shortcut[piece[num].loc];
                if(piece[num].loc > 40) break;
            }
        }
        else // onMap
        {
            piece[num].loc += 2 * val;
            if(piece[num].loc % 10 == 0 && piece[num].loc < 40)
            {
                map++;
                piece[num].onShortcut = true;
            }
        }
        if(piece[num].loc > 40)
        {
            piece[num].isDone = true;
            return 0;
        }
        if(visited[map][piece[num].loc])
        {
            isValid = false;
            return 0;
        }
        else
        {
            visited[map][piece[num].loc] = true;
            if(piece[num].loc == 40) // 40은 양쪽 공통
            {
                map ^= 1;
                visited[map][40] = true;
            }
        }
        if(piece[num].loc == 31) return 30;
        return piece[num].loc;
    }

}

📝 풀이

주어진 10개의 주사위 입력에 대해 4개의 말 중 조건에 맞는 말을 선택하여 이동시키고, 이동한 발판의 값을 누적 합 해주어 만들 수 있는 값의 최댓값을 구하는 문제입니다.
모든 경우의 수를 고려해야 하기 때문에 중복가능한 순열을 선택했고, 유효한 순열이라면 끝까지 수행하여 max_value와 비교하여 최댓값을 판별합니다.
저는 우선 map을 지름길과 정상경로 두가지로 구분하여 문제를 접근했습니다. 정상경로에서는 값이 +2씩 증가한다는 조건이 있지만 지름길은 불규칙적으로 이동하므로, 지름길의 값 변화만 따로 초기화해주고, 기존 map에서는 2 * 주사위값 만큼만 움직이도록 했습니다.
따라서 move함수 내에서는 지름길이냐 아니냐에 따라 말을 이동시키고, 문제에서 주어진 조건인 이동할 위치에 다른 말이 있는 조건에 걸린다면, 해당 순열은 성립할 수 없으므로 즉시 0을 리턴하여 제외시켜줄 수 있습니다.

📜 후기

사실 오늘 문제는 조금 올리기 민망한 문제같습니다..ㅋㅋㅋㅋㅋ
처음에 지름길과 기존 경로를 나눠버리니까 생각하지 못했던 몇 가지 예외가 발생해서 코드 사이에 억지로 예외 조건문을 껴넣게 되어버렸습니다...
만들고 보니 맵에 30 발판이 두개 중복해서 존재하기 때문에 이동할 때 예외가 발생했고, 40의 경우는 두 경로 모두가 같은 발판을 공유하므로 방문배열 사용에서 예외가 발생했습니다.
풀기 전에 이것까지 예상하긴 힘들었겠지만, 초기 접근을 잘못한 탓이지 않을까 싶어 조금 아쉬웠던 문제입니다.
우선 통과는 했으니 다음에 기회가 된다면 그날의 컨디션으로 다시 풀어볼 생각입니다.