[99클럽 코테스터디 설날 TIL / 백준] 17825 - 주사위 윷놀이 (JAVA)

99클럽 코테스터디 설날 보너스 문제 TIL
KeyWord : DFS, BackTracking, 브루트포스

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

---

풀이

내가 생각하기에 이 문제의 어려운 점은 두 가지다.

1. 점수의 최댓값을 어떻게 구할 것인가. 즉, 이 문제의 핵심이 되는 알고리즘
2. 윷놀이 판을 어떻게 구성할지

먼저 순서대로 하나씩 살펴보자.

 

방법론

고려했던 알고리즘은 총 세 가지였다.

• 그리디
• 동적 프로그래밍
• 백트래킹

일단 그리디의 경우에는 현재 턴에서 최댓값을 만드는 최선의 선택이 무엇인지 알 수 있는 방법이 없으므로 바로 생각에서 지웠다.

두 번째로 동적 프로그래밍은 사용할 수 있는 말은 네 개, 총 10턴을 진행하니, DP[4][10]이런 느낌으로 선언하면 DP로 풀 수 있지 않을까? 하는 생각이었다.

하지만 DP는 복잡한 문제를 더 작은 하위 문제로 쪼개어 해결하는 알고리즘이다. 여기서 더 작은 하위 문제로 쪼갤 수 있는 문제가 있을까... 하면, 내 눈에는 쪼갤 수 있을 법한 문제는 보이지 않았다.

 

마지막으로 백트래킹. 잠시 고민하다가 의사코드를 작성해보았다.

if (depth == 10) {  
    ans = max(ans, score);
} else {     
    기존의 말 혹은 새로운 말을 움직인다.  
    backtracking(depth + 1);     
    기존 위치로 복구.
}

이렇게 백트래킹을 이용하여 브루트포스를 하면 해를 구할 수 있을 것이다.

이렇게 했을 때 발생하기 가장 쉬운 문제는 시간 초과 혹은 메모리 초과다. 하지만 이 문제는 탐색을 진행하는 범위가 50도 안 되므로 효율성으로 인한 문제는 발생하지는 않을 것으로 보였다.

 

윷놀이 판

파란색 칸이고 빨간색 칸이고, 칸에 말이 있고 없고, 이런 걸 떠나서 윷놀이 판 자체가 깔끔하게 정리되어 있지 않으니, 일단 윷놀이 판에 번호부터 매겨보자.

이제 이 윷놀이 판을 코드 상에서 어떻게 표현할지가 문제였다.

int[] map = new int[33]; 이렇게 배열을 선언해서 사용할까? 했지만, 이렇게 하면 너무 헷갈릴 것 같았다.

일단, 말이 이동하고자 하는 칸 위에 이미 말이 있는지 확인해야 하고, 이 칸에 몇 점의 점수가 배정되어 있는지 확인해야 하며, 현재 칸이 파란색 칸인지 확인해야 하고... 일단 고려할게 너무 많았다.

그렇기에 각 칸의 정보를 저장하는 클래스를 만들어 사용하기로 했다.

static class Node {  
    int score; // 칸에 적힌 점수  
    int nextRed; // 빨간색 경로로 이동 시 다음 칸의 인덱스  
    int nextBlue; // 파란색 경로로 이동 시 다음 칸의 인덱스 (없으면 -1)  
    boolean isEmpty = true;  

    Node(int score, int nextRed, int nextBlue) {  
        this.score = score;  
        this.nextRed = nextRed;  
        this.nextBlue = nextBlue;  
    }  
}

윷놀이 판 초기화는 하드코딩이 될 수밖에 없었다. 워낙 규칙성이 없다보니 여기서 값 잘못 입력한 것 때문에 찾다가 30분은 날려먹었다.

private static void initMap() {  
    for (int i = 0; i < 20; i++) {  
        map[i] = new Node(i*2, i+1, -1);  
    }  

    map[5].nextBlue = 21;  
    map[10].nextBlue = 24;  
    map[15].nextBlue = 26;  

    map[20] = new Node(40, 32, -1);  
    map[21] = new Node(13, 22, -1);  
    map[22] = new Node(16, 23, -1);  
    map[23] = new Node(19, 29, -1);  
    map[24] = new Node(22, 25, -1);  
    map[25] = new Node(24, 29, -1);  
    map[26] = new Node(28, 27, -1);  
    map[27] = new Node(27, 28, -1);  
    map[28] = new Node(26, 29, -1);  
    map[29] = new Node(25, 30, -1);  
    map[30] = new Node(30, 31, -1);  
    map[31] = new Node(35, 20, -1);  
    map[32] = new Node(0, 32, -1);  
}  

또 말에 관한 클래스도 정의했다. 이 클래스에는 이 말의 위치와 현재까지 이 말이 획득한 점수를 저장한다.

static class Piece {  
    int score;  
    int currPos;   

    public Piece(int score, int currPos) {  
        this.score = score;  
        this.currPos = currPos;  
    }  
}  

이제 로직만 구현하면 된다. 고려할 부분이 좀 있으므로 헷갈리지 않게 정리한 후 위의 백트래킹 의사코드에 적용하면 해결할 수 있다.

---

코드

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

public class Main {    
    static class Node {  
        int score; // 칸에 적힌 점수  
        int nextRed; // 빨간색 경로로 이동 시 다음 칸의 인덱스  
        int nextBlue; // 파란색 경로로 이동 시 다음 칸의 인덱스 (없으면 -1)  
        boolean isEmpty = true;  

        Node(int score, int nextRed, int nextBlue) {  
            this.score = score;  
            this.nextRed = nextRed;  
            this.nextBlue = nextBlue;  
        }  
    }  

    static class Piece {  
        int score;  
        int currPos;   

        public Piece(int score, int currPos) {  
            this.score = score;  
            this.currPos = currPos;  
        }  
    }  

    static int[] diceValues = new int[10];  
    static Node[] map = new Node[33];  
    static Piece[] pieces = new Piece[4];  

    static int ans = 0;  

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

        initMap();  
        initPiece();  

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

        backTracking(0);  
        System.out.println(ans);  
    }

     private static void backTracking(int depth) {  
        if (depth == 10) {  
            int score = 0;  
            for (int i = 0; i < 4; i++) {  
                score += pieces[i].score;  
            }  
            ans = Math.max(ans, score);  
        } else {  
            for (int i = 0; i < 4; i++) {  
                if(pieces[i].currPos == 32)  
                    continue;  

                int diceValue = diceValues[depth];  
                int tmp = pieces[i].currPos;  

                // 파란색 칸이라면  
                if (map[pieces[i].currPos].nextBlue != -1) {  
                    diceValue--;  
                    pieces[i].currPos = map[pieces[i].currPos].nextBlue;  
                }  

                // 남은 value만큼 빨간색 화살표를 따라 이동  
                for (int j = 0; j < diceValue; j++) {  
                    pieces[i].currPos = map[pieces[i].currPos].nextRed;  
                }  

                pieces[i].score += map[pieces[i].currPos].score;  

                // 이동하고자 하는 노드가 비어있다면  
                if(map[pieces[i].currPos].isEmpty) {  
                    if(pieces[i].currPos != 32)  
                        map[pieces[i].currPos].isEmpty = false;  
                    map[tmp].isEmpty = true;  
                    backTracking(depth + 1);  
                    map[tmp].isEmpty = false;  
                    map[pieces[i].currPos].isEmpty = true;  
                }  

                pieces[i].score -= map[pieces[i].currPos].score;  
                pieces[i].currPos = tmp;  
            }  
        }  
    }

    private static void initMap() {  
        for (int i = 0; i < 20; i++) {  
            map[i] = new Node(i*2, i+1, -1);  
        }  

        map[5].nextBlue = 21;  
        map[10].nextBlue = 24;  
        map[15].nextBlue = 26;  

        map[20] = new Node(40, 32, -1);  
        map[21] = new Node(13, 22, -1);  
        map[22] = new Node(16, 23, -1);  
        map[23] = new Node(19, 29, -1);  
        map[24] = new Node(22, 25, -1);  
        map[25] = new Node(24, 29, -1);  
        map[26] = new Node(28, 27, -1);  
        map[27] = new Node(27, 28, -1);  
        map[28] = new Node(26, 29, -1);  
        map[29] = new Node(25, 30, -1);  
        map[30] = new Node(30, 31, -1);  
        map[31] = new Node(35, 20, -1);  
        map[32] = new Node(0, 32, -1);  
    }  

    private static void initPiece() {  
        for (int i = 0; i < pieces.length; i++) {  
            pieces[i] = new Piece(0, 0);  
        }  
    }  
}