[JAVA] 17825 - 주사위 윷놀이 💛2: 한땀한땀 만들어야하는 시뮬레이션 문제(집중하자...)

들어가며

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

사진과 같은 맵에서 4개의 말이 움직일 수 있다. 각 말이 도착한 곳의 점수를 획득한다. 종착점을 제외한 모든 곳에서는 말 중첩은 안된다. 10번의 주사위 값이 주어졌을 때 얻을 수 있는 최댓값을 정답으로 출력하면 되는 문제이다.

본문으로

이 문제,,, 완전탐색인 것은 알겠는데,,, 처음부터 매우 막막한 문제였다. 특히 그림의 map을 구현하는 것이 매우 어려웠다. 그리고 특히 중간으로 들어갈 수 있는 10, 20, 30에 해당하는 부분을 처리하기가 매우 난감했다.
처음에는 값 자체를 인덱스로 하는 인접리스트를 구성해서 만약 갈 곳이 2군데 이상이라면, 중간으로 들어갈지 말지를 생각했는데... 값이 인덱스가 되어버리니 중간에 있는 값들이 겹쳤다... 또 초반설계 잘못해서 시뮬레이션의 굴레에 빠져들었다..

---

이 문제는 각 노드별로 인덱스를 따로 설정해줘야하는 문제이다. 그렇치 않으면 구현자체가 너무너무 힘들어진다. 그래서 아래 로직과 같이 각 칸의 점수(score) 다음칸(next) 안으로 들어가는 파란색 화살표인지(blue)를 담는 전역배열을 각각 선언해서, 정말 한땀한땀 인덱싱을 해주었다.

public class Main {

    static final int FINISH = 32;

    static int[] dice = new int[10];
    static int[] score = new int[33]; // 각 칸의 점수
    static int[] next = new int[33];  // 빨간 화살표 기준 다음 칸
    static int[] blue = new int[33];  // 파란 화살표 시작 칸이면 그 다음 칸
    static int answer = 0;

    static void initBoard() {
        // 0 : 시작
        // 1 ~ 20 : 바깥길 (2,4,6,...,40)
        // 21 ~ 23 : 10에서 파란길 (13,16,19)
        // 24 ~ 25 : 20에서 파란길 (22,24)
        // 26 ~ 28 : 30에서 파란길 (28,27,26)
        // 29 ~ 31 : 공통길 (25,30,35)
        // 32 : 도착

        // 시작, 도착
        score[0] = 0;
        score[FINISH] = 0;

        // 바깥길 점수 세팅
        for (int i = 1; i <= 20; i++) {
            score[i] = i * 2; // 2,4,6,...,40
        }

        // 바깥길 next
        for (int i = 0; i < 20; i++) {
            next[i] = i + 1;
        }
        next[20] = FINISH; // 40 다음은 도착

        // 10에서 파란길: 13 -> 16 -> 19 -> 25
        score[21] = 13;
        score[22] = 16;
        score[23] = 19;
        next[21] = 22;
        next[22] = 23;
        next[23] = 29;

        // 20에서 파란길: 22 -> 24 -> 25
        score[24] = 22;
        score[25] = 24;
        next[24] = 25;
        next[25] = 29;

        // 30에서 파란길: 28 -> 27 -> 26 -> 25
        score[26] = 28;
        score[27] = 27;
        score[28] = 26;
        next[26] = 27;
        next[27] = 28;
        next[28] = 29;

        // 공통길: 25 -> 30 -> 35 -> 40 -> 도착
        score[29] = 25;
        score[30] = 30;
        score[31] = 35;
        next[29] = 30;
        next[30] = 31;
        next[31] = 20; // 공통길의 35 다음은 바깥길의 40(노드 20)

        // 파란 화살표
        blue[5] = 21;   // 바깥길 10에서 출발하면 13으로
        blue[10] = 24;  // 바깥길 20에서 출발하면 22로
        blue[15] = 26;  // 바깥길 30에서 출발하면 28로
    }

    static int move(int start, int dist) {
        if (start == FINISH) {
            return FINISH;
        }

        int cur = start;

        // 첫 한 칸만 파란 화살표 가능
        if (blue[cur] != 0) {
            cur = blue[cur];
            dist--;
        } else {
            cur = next[cur];
            dist--;
        }

        // 나머지는 빨간 화살표만 따라감
        while (dist > 0 && cur != FINISH) {
            cur = next[cur];
            dist--;
        }

        return cur;
    }

    static void dfs(int turn, int[] horse, int sum) {
        if (turn == 10) {
            answer = Math.max(answer, sum);
            return;
        }

        int dist = dice[turn];

        for (int i = 0; i < 4; i++) {
            int cur = horse[i];

            // 이미 도착한 말은 못 움직임
            if (cur == FINISH) {
                continue;
            }

            int nxt = move(cur, dist);

            // 도착 칸이 아니면 다른 말과 겹치면 안 됨
            if (nxt != FINISH) {
                boolean conflict = false;
                for (int j = 0; j < 4; j++) {
                    if (i == j) {
                        continue;
                    }
                    if (horse[j] == nxt) {
                        conflict = true;
                        break;
                    }
                }
                if (conflict) {
                    continue;
                }
            }

            horse[i] = nxt;
            dfs(turn + 1, horse, sum + score[nxt]);
            horse[i] = cur; // 백트래킹
        }
    }

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

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

        initBoard();

        int[] horse = new int[4]; // 말 4개 모두 시작 칸(0)
        dfs(0, horse, 0);

        System.out.println(answer);
    }
}

---

맞긴 했지만, 인접리스트를 활용하면 조금 더 깔끔하게 모델링 할 수 있을 것 같다. 인덱싱을 따로 하되, 인접리스트를 활용하면 시작부분에서 길이 2개 이상이면 안쪽으로 들어가게 하는 로직을 손쉽게 유도할 수 있는 것 같다. 아래는 인접리스트를 활용한 풀이이다.

public class Main {

    static final int FINISH = 100;

    static int[] dice = new int[10];
    static int[] horse = new int[4];
    static int[] score = new int[101];
    static ArrayList<Integer>[] adj = new ArrayList[101];

    static void add(int from, int to) {
        adj[from].add(to);
    }

    static void setMap() {
        for (int i = 0; i <= 100; i++) {
            adj[i] = new ArrayList<>();
        }

        // 바깥길: 0 -> 1 -> 2 -> ... -> 20 -> FINISH
        for (int i = 0; i <= 19; i++) {
            add(i, i + 1);
        }
        add(20, FINISH);

        // 10에서 파란길: 5 -> 21 -> 22 -> 23 -> 24
        add(5, 21);
        add(21, 22);
        add(22, 23);
        add(23, 24);

        // 20에서 파란길: 10 -> 27 -> 28 -> 24
        add(10, 27);
        add(27, 28);
        add(28, 24);

        // 30에서 파란길: 15 -> 29 -> 30 -> 31 -> 24
        add(15, 29);
        add(29, 30);
        add(30, 31);
        add(31, 24);

        // 공통길: 24 -> 25 -> 26 -> 20 -> FINISH
        add(24, 25);
        add(25, 26);
        add(26, 20);

        // 점수 세팅
        score[1] = 2;
        score[2] = 4;
        score[3] = 6;
        score[4] = 8;
        score[5] = 10;
        score[6] = 12;
        score[7] = 14;
        score[8] = 16;
        score[9] = 18;
        score[10] = 20;
        score[11] = 22;
        score[12] = 24;
        score[13] = 26;
        score[14] = 28;
        score[15] = 30;
        score[16] = 32;
        score[17] = 34;
        score[18] = 36;
        score[19] = 38;
        score[20] = 40;

        score[21] = 13;
        score[22] = 16;
        score[23] = 19;
        score[24] = 25;
        score[25] = 30;
        score[26] = 35;

        score[27] = 22;
        score[28] = 24;

        score[29] = 28;
        score[30] = 27;
        score[31] = 26;

        score[FINISH] = 0;
    }

    static int move(int start, int dist) {
        if (start == FINISH) {
            return FINISH;
        }

        int cur = start;

        // 첫 한 칸만 파란길 가능
        if (adj[cur].size() >= 2) {
            cur = adj[cur].get(1);
            dist--;
        } else {
            cur = adj[cur].get(0);
            dist--;
        }

        // 이후는 빨간길만
        while (dist > 0 && cur != FINISH) {
            cur = adj[cur].get(0);
            dist--;
        }

        return cur;
    }

    static boolean isOccupied(int nxt, int idx) {
        if (nxt == FINISH) {
            return false;
        }

        for (int i = 0; i < 4; i++) {
            if (i == idx) continue;
            if (horse[i] == nxt) return true;
        }
        return false;
    }

    static int dfs(int turn) {
        if (turn == 10) {
            return 0;
        }

        int ret = 0;

        for (int i = 0; i < 4; i++) {
            int cur = horse[i];
            int nxt = move(cur, dice[turn]);

            if (isOccupied(nxt, i)) continue;

            horse[i] = nxt;
            ret = Math.max(ret, score[nxt] + dfs(turn + 1));
            horse[i] = cur;
        }

        return ret;
    }

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

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

        setMap();
        System.out.println(dfs(0));
    }
}

마무리하며

하~~ 정말 시뮬레이션 문제 집중 안하고 풀면 실수하기가 쉬운 것 같다. 이 또한 나의 실력과 연습이 부족한 탓이겠지.... 특히 값을 인덱스로 할지 말지를 정하는 것은 한발짝 물러나 판단을 할 필요가 있는 것 같다. 간단하게 가려다가, 망했다..

 

그리고 이 문제는 30분 생각하다가 3시간짜리 수업듣고 또 30분 생각하고 할일이 생겨서 다음날 풀었는데,,, 너무 질질 끌린 것 같다. 시뮬레이션 문제는 꼭 시간재고 한번에 푸는 연습을 하자! 파이팅 🔥