[JAVA] 백준 주사위 윷놀이

단순 구현문제인줄 알았는데, 연결리스트를 통한 구현이어서 어려웠다.

 

노드는 아래 그림과 같이 순서대로 연결한다.

https://zoosso.tistory.com/232

1. 직선방향으로 시작~도착까지 Node.next(연결된 객체1)로 연결

 

2. 지름길 같은경우는 addNext를 통해 10,20,30에 해당하는 노드를 찾아서 Node.fastPath(연결되 객체2)에 연결해준다.

 

3. permutation을 통해서 order[] 배열에 순열 경우의수를 dfs로 탐색한다.

 

4. dfs로 깊이 10까지 채웠으면, 해당 order[]배열을 통해 order[i]번째에 해당하는 Node[] horse에 넣어주는 gamestart를 시행한다.

 

5. 한가지 order경우의 수에 대해 gamestart를 완료했으면, Max값과 방문한 노드값들의 합(gamestart메소드 return값)을 비교해준다.

 

6. permutation이므로 order dfs(depth=11)일때 모든경우에 대하여 방문노드 합을 비교하여 최대값을 알아낸다.

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int[] dice, order; // 주사위, 배치순서
    private static Node[] horse; // 4개의 말
    private static Node start; // 시작지점
    private static int answer = Integer.MIN_VALUE;

    static class Node {   // 윷놀이 판을 연결 리스트 구조에 담는다.
        int score;        // 윷놀이판에서 해당 칸의 점수.
        boolean isEmpty;  // 해당 칸이 비었는지. (다른 말이 와있는 칸인지 체크)
        boolean isFinish; // 도착 지점인지를 체크.
        Node next;
        Node fastPath;    // 윷놀이판에서 10, 20, 30은 두 가지 방향이 존재한다.

        public Node(int score) {
            this.score = score;
            this.isEmpty = true;
        }

        // 노드 연결 (연결 리스트 구조)
        public Node addNext(int score) {
            Node nextNode = new Node(score);
            this.next = nextNode;
            return nextNode;
        }

        // 노드 찾기 (지름길 놓는 지점을 찾기 위한 함수)
        public static Node getNode(Node start, int target) {
            Node temp = start;
            while (true) { // 시작 지점부터 탐색해가며 특정 노드를 찾습니다.
                if (temp == null) return null;
                if (temp.score == target) return temp;
                temp = temp.next;
            }
        }
    }

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

        dice = new int[10 + 1];
        order = new int[10 + 1];
        horse = new Node[4 + 1];
        for (int i = 1; i <= 10; i++) {
            dice[i] = Integer.parseInt(st.nextToken());
        }

        init(); // 윷놀이판 설정
        permutation(1); // 10개의 주사위 결과를 말들에게 할당
        System.out.println(answer);
    }

    private static void permutation(int depth) {//order에 순열순서 재귀로 넣음
        if (depth >= 11) {
            answer = Math.max(answer, gameStart());
            return;
        }

        for (int i = 1; i <= 4; i++) {
            order[depth] = i;
            permutation(depth + 1);
        }
    }

    private static int gameStart() {
        Arrays.fill(horse, start); // 말들을 시작 지점으로 배치

        int score = 0;
        for (int i = 1; i <= 10; i++) {
            Node cur = horse[order[i]]; // !!!순열로 할당된 순서대로 말들을 움직입니다.!!!
            cur.isEmpty = true; // 현재 있는 칸을 비워줍니다.

            for (int j = 1; j <= dice[i]; j++) { // 주사위에 나온 수치만큼 이동합니다.
                if (j == 1 && cur.fastPath != null) { // 처음 이동을 시작하려는 위치가 파란색 칸이라면.
                    cur = cur.fastPath; // 지름길로 이동(파란색 방향)
                } else {
                    cur = cur.next; // 빨간색 방향으로 이동
                }
            }

            horse[order[i]] = cur; // 이동 후, 말 위치 설정

            if (!cur.isEmpty && !cur.isFinish) { // 이동을 마친 칸에 다른 말이 있다면, 해당 말은 고를 수 없다.
                score = 0; // 주사위에 할당받은 말들의 순서가 무효처리.
                break;
            } else {
                cur.isEmpty = false; // 말이 존재하는 것으로 표시
                score += cur.score; // 해당 칸의 점수 추가
            }
        } // 게임종료

        // 다음 게임을 위해 말들의 위치를 지워줍니다.
        for (int i = 1; i <= 4; i++)
            horse[i].isEmpty = true;

        return score; // 획든한 점수 반환
    }

    private static void init() {
        start = new Node(0); // 시작 지점. (시작 지점의 스코어는 0)

        Node temp = start;
        for (int i = 2; i <= 40; i += 2) {
            temp = temp.addNext(i); // 윷놀이판 바깥쪽 경로 설정
        }

        Node end = temp.addNext(0); // 도착 지점. (도착 지점의 스코어는 0)
        end.isFinish = true;
        end.next = end; // 자기자신을 가르키도록 설정 (도착 지점을 넘어서는 이동에 대해 NPE 방지)

        Node crossroads = new Node(25); // 가운데 교차점 (score = 25)

        // 교차점(25) -> 30 -> 35 -> 40
        temp = crossroads.addNext(30);
        temp = temp.addNext(35);
        temp.next = Node.getNode(start, 40);

        // 10 -> 13 -> 16 -> 19 -> 25(교차점)
        temp = Node.getNode(start, 10);
        temp = temp.fastPath = new Node(13);
        temp = temp.addNext(16);
        temp = temp.addNext(19);
        temp.next = crossroads;

        // 20 -> 22 -> 24 -> 25(교차점)
        temp = Node.getNode(start, 20);
        temp = temp.fastPath = new Node(22);
        temp = temp.addNext(24);
        temp.next = crossroads;

        // 30 -> 28 -> 27 -> 26 -> 25(교차점)
        temp = Node.getNode(start, 30);
        temp = temp.fastPath = new Node(28);
        temp = temp.addNext(27);
        temp = temp.addNext(26);
        temp.next = crossroads;
    }
}