Baekjoon[17825] - 주사위 윷놀이

링크

17825번: 주사위 윷놀이

문제설명

• 윷놀이 모든 경우의 수 중 최대값

문제풀이

• 완전탐색
• map 설정

문제코드

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main17825_COMB {

    public static int[][] map = {    //{value,next,specialnext}
            {0,1},    //시작
            {2,2},    
            {4,3},    
            {6,4},    
            {8,5},    
            {10,6,22},    //#5
            {12,7},    
            {14,8},    
            {16,9},    
            {18,10},    
            {20,11,25},    //#
            {22,12},    
            {24,13},    
            {26,14},    
            {28,15},    
            {30,16,27},    
            {32,17},    
            {34,18},    
            {36,19},    
            {38,20},    
            {40,21},    //#20    
            {0,-1},        //끝

            {13,23},    //#22
            {16,24},    
            {19,30},

            {22,26},    //#25    
            {24,30},

            {28,28},    //#27
            {27,29},    
            {26,30},

            {25,31},    //#30    
            {30,32},    
            {35,20},    
    };
    public static boolean visited[];

    public static int Ans=Integer.MIN_VALUE;
    public static int Temp=0;

    public static int[] move = new int[10];
    public static int[] serial = new int[10];

    public static void Search(int cnt) {
        if(cnt==10) {
//            System.out.println(Arrays.toString(serial));
//            윷놀이 시뮬레이션
            Temp=0;
            visited = new boolean[33];
            Simulation();
            if(Ans<Temp) {
                int a=1;
            }
            Ans = Math.max(Ans, Temp);
            return;
        }

        for (int i = 0; i < 4; i++) {
            serial[cnt]=i;
            Search(cnt+1);
        }
    }

    public static void Simulation() {
        int[] horse = new int[]{0,0,0,0};
        int start=0;
        for (int idx = 0; idx < 10; idx++) {
            visited[horse[serial[idx]]]=false;
            for (int m = 0; m < move[idx]; m++) {
//                움직이는도중 도착함
                if(horse[serial[idx]]==21) {
                    break;
                }
//                움직이기
//                파란색 칸일 때
                if(m==0 && map[horse[serial[idx]]].length==3) {
                    horse[serial[idx]] = map[horse[serial[idx]]][2];
                }
                else {
                    horse[serial[idx]] = map[horse[serial[idx]]][1];
                }
            }
//            움직임 끝났으면
//            도착한 칸에 말이 없어야 함.(마지막 칸 제외)
//            말이 없으면
            if(!visited[horse[serial[idx]]] || horse[serial[idx]]==21) {
                visited[horse[serial[idx]]]=true;
                Temp+=map[horse[serial[idx]]][0];
            }
//            말이 있으면 이 serial은 무효
            else {
                Temp=-1;
                return;
            }
        }
    }


    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("res/baekjoon/17825.txt"));
        Scanner sc = new Scanner(System.in);

        for (int i = 0; i < 10; i++) {
            move[i] = sc.nextInt();
        }

        Search(0);
//        serial = new int[] {0,0,0,1,1,1,2,2,2,3};
//        visited = new boolean[33];
//        Simulation();
//        System.out.println(Temp);
//        


        System.out.println(Ans);
//        초기화
        Ans=Integer.MIN_VALUE;
        Temp=0;
    }
}

아쉬운점

• 모든 경우의 말의 순서를 미리 짜놓고 그에 맞추어서 Simulation을 돌리면서 백트래킹하였음.
  • 아예 처음부터 DFS돌리면 훨씬 빠름.
  • 이 경우는 O(N)이 계산상 터지지 않아서 문제는 없었음
    • 야구나, 보호필름같은 경우는 DFS안하면 터짐
• simulation중 index 실수
  • idx가 아니라 serial[idx]써야함
• 덜 꼼꼼했음 (예외처리 제대로 안해줌)
  • 도착한 칸에 말이 있는 경우 예외처리 해줘야 함.
  • 도착한 칸에 말이 없어야 함.(마지막 칸 제외)

잘한점

• O(N) = 4^10*50 = 5*10^7
• map설정을 어떻게 할까 고민했었음
  • node형식으로 만듬
    • {현재 value, 다음 칸, special경로로 가는 다음 칸}
  • 주사위 갯수에 따른 다음칸 으로 설정하면 공간복잡도*5지만 시간복잡도/5임
    • {현재 value, 1칸뒤, 2칸뒤, 3칸뒤, 4칸뒤, 5칸뒤}
• 1시간