백준 17825번: 주사위 윷놀이

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

17825번: 주사위 윷놀이

문제

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

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

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

입력

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

출력

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

 

---

 

풀이 1. 브루트포스

4개의 말을 10번 이동시키는 총 경우의 수는 4^10 == 2^20번이다. 그리고 각 경우마다 10번의 움직임이 있으니, 대략 수천만 번의 연산이 이루어진다. 

 

1) 경우의 수 줄이기: 4개의 말은 서로 구분되지 않는다는 점을 이용한다.

• 간단하게 생각하면, 처음 출발하는 말을 0번째 말로 고정해도 상관없다. -> 4배 단축
• (더 자세하게 나눌수도 있을 것이다: 근데 머리가 굳어서 생각이 잘 안 돌아가네...)

 

2) 맵을 경로로 표현

• 외각을 도는 경로를 0번째 route, 첫 번째 파란 화살표를 타고가는 경로를 1번째 route, 두 번째 파란 화살표를 타고 가는 경로를 2번째 route, 세 번째 파란 화살표를 타고 가는 경로를 3번째 route로 정의하였다.
• 경로의 각 위치(:="location")마다의 값을 int array에 저장하였다.
• 1, 2, 3번째 route의 시작점은 환승점으로 설정하였다.
• 도착점이 존재하며, 도착점에 도착할 경우 값을 더하지 않기 때문에 도착점 location에서의 값은 0으로, 모든 route 배열의 맨 마지막에 저장하였다.

 

3) 말(:="Unit")을 표현

• 말 class를 "Unit"이라는 이름으로 만들었다.
• Unit은 route(0~3번 route 중 어느 route를 이용하는지). location(각 route에서 몇 번째 장소에 있는지), isEnd(도착점에 도착했는지 boolean값으로)이라는 변수를 가지고 있으며, 기본적으로 (0, 0, false)값을 갖는다.

 

4) 이동을 표현

• 4^9번의 경우를 다 탐색하므로, 비스마스킹으로 각 경우를 나누었다. 1)에서의 논의에 따라, 첫 번째 움직임은 0번째 말이 고정적으로 움직인다.
• 이동하려는 말이 이미 도착점에 있는 경우: 도착점에 있는 말을 움직이려고 하는 경우이므로, 해당 경우의 수는 invalid하다: 다음 경우로 넘어간다.
• 환승점에 도달한 경우: route와 location을 바꿔준다. 예를 들어, (route, location)이 (0, 5)인 경우는 첫 번째 환승 route를 타게 되므로, (1, 0)으로 나타낸다.
• 선택한 말을 움직이니 도착점 이상으로 갔을 경우: location을 도착점으로 바꿔주며, 해당 말의 isEnd 값을 true로 바꾼다.
• 이동했더니 이미 다른 말이 해당 위치에 있는 경우: invalid한 case이니 다음 경우로 넘어간다.

 

 

5) 해당 위치에 있는지 확인하기: 두 말의 위치가 동일한지 판단해야 한다.

 

naive한 생각에 따른 오답 2가지(참고: 나는 둘 다 해봤다가 틀렸다;;)

1. "(route, location)값이 같으면 같다" -> (1, 6), (2, 5), (3, 6) 모두 '35' 위치를 가르킨다
2. "발판의 위치 값이 같으면 같다" -> 그림보면 알겠지만 '30'은 2군데에 있다.

이를 보완하는 방법

1. 대부분의 위치에서는 (route, location) 값이 같으면 같다. 환승점도 무조건 location이 0이 되도록 바꿔주어 저장했기에, 환승점의 (route, location) 표현 값은 동일하다.
2. 문제가 되는 위치: 25, 30, 35, 40임을 알 수 있다.
3. 25, 35, 40의 경우, 중복되는 값을 갖는 발판이 없으므로 두 말의 위치에 따른 발판의 값이 25, 35, 혹은 40으로 같은지 확인하면 된다.
4. 30의 경우: 값만 확인하면 안 된다! (1, 5), (2, 4), (3, 5)는 동일한 위치, (3, 0)은 다른 위치다: location이 0인 경우와 아닌 경우로 나눠서 처리하자.

 

배운 점

1. 문제 대충 읽지 말자.

2. 경로가 동일한 경우를, 그림을 보면서 조금 찬찬히 생각하면 더 빨리 설계할 수 있지 않았을까?

3. location같은 건 loc으로 쓰자: 너무 길어...

 

 

코드

import java.io.*;
import java.util.*;

public class Baekjoon17825_주사위윷놀이 {
    static List<int[]> route;

    public static void main(String[] args) throws IOException{
        int[] route0 = {-1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0};
        int[] route1 = {10, 13, 16, 19, 25, 30, 35, 40, 0};
        int[] route2 = {20, 22, 24, 25, 30, 35, 40, 0};
        int[] route3 = {30, 28, 27, 26, 25, 30, 35, 40, 0};
        route = new ArrayList<>();
        route.add(route0);
        route.add(route1);
        route.add(route2);
        route.add(route3);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] moves = new int[10];
        for (int i = 0; i < 10; i++) {
            moves[i] = Integer.parseInt(st.nextToken());
        }

        int ans = 0;
        outer: for (int i = 0; i < (1<<18); i++) {
            List<Unit> units = new ArrayList<>();
            for (int j = 0; j < 4; j++) {
                units.add(new Unit());
            }
            int choose = i;
            int temp = 0;
            for (int j = 0; j < 10; j++) {
                Unit curUnit = (j == 0)? units.get(0): units.get(choose & ((1<<2)-1));
                if (curUnit.isEnd) continue outer; 

                curUnit.location += moves[j];
                if ((curUnit.location == 5 || curUnit.location == 10 || curUnit.location == 15) && curUnit.route == 0) {
                    curUnit.route += (curUnit.location / 5);
                    curUnit.location = 0;
                }

                if ((curUnit.route == 0 && curUnit.location > 20) || (curUnit.route == 2 && curUnit.location > 6) 
                        || (curUnit.route % 2 == 1 && curUnit.location > 7)) {
                    curUnit.isEnd = true;
                    curUnit.location = route.get(curUnit.route).length-1;
                }

                if (!curUnit.isEnd) {
                    for (int k = 0; k < 4; k++) {
                        if (j == 0) continue; 
                        if (k == (choose & ((1<<2)-1))) continue;
                        if (isSameLocation(curUnit, units.get(k))) continue outer;
                    }
                }

                temp += route.get(curUnit.route)[curUnit.location];
                if (j > 0) choose>>=2;
            }

            ans = Math.max(temp, ans);
        }

        System.out.println(ans);
    }

    static class Unit {
        int location;
        int route;
        boolean isEnd;

        public Unit() {
            location = 0;
            route = 0;
            isEnd = false;
        }
    }

    static boolean isSameLocation(Unit u1, Unit u2) {
        if (route.get(u1.route)[u1.location] == 25 || route.get(u1.route)[u1.location] == 35 
            || route.get(u1.route)[u1.location] == 40) {
            return route.get(u1.route)[u1.location] == route.get(u2.route)[u2.location];
        } else if (route.get(u1.route)[u1.location] == 30 && route.get(u2.route)[u2.location] == 30) {
            return (u1.location == 0 && u2.location == 0) || (u1.location > 0 && u2.location > 0);
        }
        return (u1.route == u2.route && u1.location == u2.location);
    }
}

 

 

 

 

풀이 1. 백트래킹

나름 열심히 풀었고 최적화도 살짝 생각해봤다. 그런데 사실 백트래킹이 훨씬 빠르다. TODO