99클럽 코테 스터디 7일차 TIL 백트래킹(주사위 윷놀이)

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

 

사용 알고리즘

구현, 백트래킹

 

아이디어

1. 분기점을 기준으로 경로를 나누어 배열에 점수 저장

2. dfs로 각 말이 움직였을 경우 탐색

2-1. 분기점처리, 도착점에 이전 말이 있을 경우 처리(도착점이 40을 넘어갔을 때는 제외)

3.점 수 합의 최댓값으로 갱신

 

유의점

1. 깊은복사로 말 위치 원상복귀

2. 10/20/30 분기점에다가 25 이후의 길을 각각 설정한다면 말이 겹치는 경우 찾기 어려움..

 

제출코드

package BOJ.Implementation;


import com.sun.security.jgss.GSSUtil;

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

public class BOJ_17825_주사위윷놀이 {

    static class Point{
        int type;
        int x;
        Point(int type, int x){
            this.type = type;
            this.x = x;
        }
    }

    static int[] arr0 = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40};
    static int[] arr10 = {10, 13, 16, 19};
    static int[] arr20 = {20, 22, 24};
    static int[] arr30 = {30, 28, 27, 26};
    static int[] arr50 = {25, 30, 35, 40};
    static Point[] horse;
    static int[] dice;
    static int maxSum;

    public static int move(Point p, int[] arr, int num){
        int sum = 0;

        // 현재 상태 저장
        Point origin = new Point(p.type, p.x);

        int next = p.x + num;

        // 탈출한 경우 (0코스, 50코스 일때)
        if((p.type == 0 || p.type == 50) && next >= arr.length) {
            p.type = -1;
            return 0;
        }else {
            if((p.type == 10 || p.type == 20 || p.type == 30) && next >= arr.length){
                p.type = 50;
                int nx = next - arr.length;
                if(nx < 4) {
                    p.x = nx;
                    sum += arr50[p.x];
                } else {
                    p.type = -1;
                    return 0;
                }
            }else{
                sum += arr[next];
                p.x = next;
                // 다른 루트를 타는 경우
                if(arr[p.x] == 10 && p.type == 0) {
                    p.type = 10;
                    p.x = 0;
                } else if(arr[p.x] == 20 && p.type == 0) {
                    p.type = 20;
                    p.x = 0;
                } else if(arr[p.x] == 30 && p.type == 0) {
                    p.type = 30;
                    p.x = 0;
                }
            }
        }

        // 겹침 확인
        for (Point h : horse) {
            if (h == p) continue;
            if (h.type == -1) continue;

            // 겹치는 경우: 같은 경로와 위치
            if (h.type == p.type && h.x == p.x) {
                p.type = origin.type;
                p.x = origin.x;
                return -1;
            }

            // 경로가 다른 경우, 숫자 값이 동일한지 확인
            int now = 0, other = 0;
            if (p.type == 0) now = arr0[p.x];
            else if (p.type == 10) now = arr10[p.x];
            else if (p.type == 20) now = arr20[p.x];
            else if (p.type == 30) now = arr30[p.x];
            else if (p.type == 50) now = arr50[p.x];

            if (h.type == 0) other = arr0[h.x];
            else if (h.type == 10) other = arr10[h.x];
            else if (h.type == 20) other = arr20[h.x];
            else if (h.type == 30) other = arr30[h.x];
            else if (h.type == 50) other = arr50[h.x];

            // 숫자 값이 같으면 겹친 것으로 봄
            if (now == other) {
                p.type = origin.type;
                p.x = origin.x;
                return -1;
            }
        }

        return sum;
    }

    public static int route(Point p, int num){
        int tmp = 0;
        // 1. arr0 루트 타는 경우
        if(p.type == 0) tmp = move(p, arr0, num);
        // 2. arr10 루트 타는 경우
        else if(p.type == 10) tmp = move(p, arr10, num);
        // 3. arr20 루트 타는 경우
        else if(p.type == 20) tmp = move(p, arr20, num);
        // 4. arr30 루트 타는 경우
        else if(p.type == 30) tmp = move(p, arr30, num);
        // 5. arr50 루트 타는 경ㅇ
        else if(p.type == 50) tmp = move(p, arr50, num);
        return tmp;
    }

    public static void dfs(int now, int sum){
        if(now == 10){
            maxSum = Math.max(maxSum, sum);
            return;
        }
        // 모든 말에 대해 값 구하기
        for(int i=0; i<4; i++){
            // 도착한 말 제외
            if(horse[i].type == -1) continue;
            // 기존 상태 저장
            Point origin = new Point(horse[i].type, horse[i].x);
            int tmp = route(horse[i], dice[now]);
            // 겹쳤었던 경우
            if(tmp == -1) continue;
            dfs(now+1, sum+tmp);
            // 위치 원상복귀
            horse[i].type = origin.type;
            horse[i].x = origin.x;
        }
    }

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

        // 주사위 정보 저장
        dice = new int[10];
        for(int i=0; i<10; i++) {
            int d = Integer.parseInt(st.nextToken());
            dice[i] = d;
        }

        // 말 정보 저장
        horse = new Point[4];
        for(int i=0; i<4; i++){
            horse[i] = new Point(0, 0);
        }

        dfs(0, 0);

        System.out.println(maxSum);
    }
}