[BJ]17825. 주사위 윷놀이

BJ G2 17825 주사위 윷놀이

 

 

문제링크

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

17825번: 주사위 윷놀이

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/5ARJOwvb9hc

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l2;

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

/**
 * 윷놀이판을 자료구조로 만든 후 중복 순열로 말들의 순서를 잡아가면서 완탐하기!
 * 
 * @author 은서파
 * @since 2022/04/04
 * @see https://www.acmicpc.net/problem/17825
 * @performance 12920 132
 * @category #시뮬레이션
 * @note
 */

public class BJ_G2_17825_주사위윷놀이 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;

    private static LinkNode startNode, endNode;
    private static int[] dices;
    private static Horse[] horses;

    private static int MAX = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        setup();
        input = new BufferedReader(new StringReader(src));
        dices = new int[10];
        tokens = new StringTokenizer(input.readLine());
        for (int i = 0; i < dices.length; i++) {
            dices[i] = Integer.parseInt(tokens.nextToken());
        }

        // 게임 시작
        horses = new Horse[4];
        for (int i = 0; i < horses.length; i++) {
            horses[i] = new Horse();
        }

        makePermutationDup(0, 0);

        System.out.println(MAX);
    }

    /**
     * 주사위에 해당하는 말을 결정하는 중복 순열 구하기
     * 
     * @param choose
     * @param score
     */
    private static void makePermutationDup(int choose, int score) {
        // 기저 조건
        if (choose == 10) {
            MAX = Math.max(MAX, score);
            return;
        }

        // 재귀 상황 - 자식 노드 탐색
        for (int i = 0; i < 4; i++) {
            // 말 선택 - 이미 도착지점에 있는 말? 선택 불가 - 다음 말 선택
            Horse h = horses[i];
            if (h.isDone) {
                continue;
            }
            // 갈수 있는지 살펴보자.
            int dice = dices[choose];
            LinkNode next = h.node;
            for (int d = 0; d < dice; d++) {
                if (d == 0 && next.blueNext != null) {
                    next = next.blueNext;
                } else {
                    next = next.redNext;
                }
                // 다음 지점에 종료지점이면 그냥 끝
                if (next.equals(endNode)) {
                    break;
                }
            } // 다음 지점 결정 완료 - 갈수 있으려면? 그 지점에 다른 말이 없어야 한다.
            if (next != endNode && next.horse != null) {
                continue;
            }

            // 상태 변경 후
            boolean isDone = h.isDone;
            if (next.equals(endNode)) {
                h.isDone = true;
            }
            // 기존 link --> next로 변경
            LinkNode current = h.node;
            current.horse = null;
            next.horse = h;
            h.node = next;

            // 다음 재귀
            makePermutationDup(choose + 1, score + next.score);

            // 상태 원복
            h.isDone = isDone;
            h.node = current;
            current.horse = h;
            next.horse = null;

        }
    }

    /**
     * 게임판 완성
     */
    private static void setup() {
        startNode = new LinkNode(0);
        endNode = new LinkNode(0);
        LinkNode crossNode = new LinkNode(25);

        // 가장 외곽의 빨간색 노드 설정
        LinkNode pre = startNode;
        for (int i = 1; i < 21; i++) {
            pre.redNext = new LinkNode(i * 2);
            if (i == 6) {
                // pre에 blueNext 추가
                pre.blueNext = new LinkNode(13);
                shortPath(pre.blueNext, crossNode, 3, 2);
            } else if (i == 11) {
                pre.blueNext = new LinkNode(22);
                shortPath(pre.blueNext, crossNode, 2, 1);
            } else if (i == 16) {
                pre.blueNext = new LinkNode(28);
                shortPath(pre.blueNext, crossNode, -1, 2);
            }
            pre = pre.redNext;
        }
        pre.redNext = endNode;
        shortPath(crossNode, pre, 5, 2);
    }

    private static void shortPath(LinkNode sNode, LinkNode tNode, int step, int count) {
        for (int i = 0; i < count; i++) {
            sNode.redNext = new LinkNode(sNode.score + step);
            sNode = sNode.redNext;
        }
        sNode.redNext = tNode;
    }

    static class LinkNode {
        int score;
        LinkNode redNext;
        LinkNode blueNext;
        Horse horse;

        public LinkNode(int score) {
            this.score = score;
        }
    }

    static class Horse {
        boolean isDone; // 이미 도착지점에 왔는가?
        LinkNode node = startNode;
    }

    // REMOVE_START
    private static String src = "1 2 3 4 1 2 3 4 1 2";
    // REMOVE_END
}