[백준] code.plus(브루트 포스 Part 2,JAVA)17825번, 주사위 윷놀이

문제 링크

17825번: 주사위 윷놀이

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 주사위는 5면체로 되어있습니다.

2. 빨간색 칸에는 빨간색 화살표, 파란색 칸에는 파란색 화살표로 이동합니다.

3. 칸을 이동할 때 해당 칸에 다른 말이 존재하면 이동하지 못합니다.

4. 말이 이동하였을 때 도착한 칸의 숫자를 점수에 저장합니다.

5. 주사위를 10번 던져서 4개의 말을 이동할 때 최대 점수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 10턴동안 말을 이동하는 모든 경우를 탐색합니다.

 

3. 모든 경우 탐색 후 얻은 최대 점수를 결과로 출력합니다.

 

윷놀이 판.

외부

 

저는 시작 ~ 40까지 2씩 증가하는 칸들을 외부로 설정하였습니다.

해당 칸을 이동할 때에는 현재 칸 + (2 × 주사위 숫자)으로 이동합니다.

 

외부에서 10, 20, 30일 때

 

파란색 칸으로써 파란색 화살표로 이동하기 때문에 외부에서 내부로 이동합니다.

 

내부

 

외부와 내부의 중복된 숫자(22, 24, 26, 28..)이 있기 때문에 내부로 만들어서 따로 구분하였습니다.

칸을 이동하는 것은 현재 있는 칸에 따라 이동하도록 하였습니다.

 

13, 16, 19 : +3

 

22, 24 : +2

 

28, 27, 26 : -1

 

※각 범위를 벗어나면 25를 지나가거나 도착하기 때문에 따로 칸을 조정하면서 진행해야 합니다.

 

 

 

예제입력 2.

 

※최대의 경우만 탐색하는 과정을 보여드리겠습니다.

 

첫 번째 주사위 던지는 값은 어떤 말이 출발하든 상관이 없으므로 저는 1번째 말을 이동하도록 하였습니다.

 

1. 입력되는 정보들을 저장합니다.

 

1 1 1 1 1 1 1 1 1 1

 

2. 10턴동안 말을 이동하는 모든 경우를 탐색합니다.

 

1번째 주사위 던지기

2번째 주사위 던지기

3번째 주사위 던지기

4번째 주사위 던지기

5번째 주사위 던지기

6번째 주사위 던지기

7번째 주사위 던지기

8번째 주사위 던지기

9번째 주사위 던지기

10번째 주사위 던지기

3. 모든 경우 탐색 후 얻은 최대 점수를 결과로 출력합니다.

 

최대값 133을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 주사위의 정보를 띄어쓰기 기준 나누었습니다.
• 첫 번째 주사위는 1번째 말이 이동하도록 설정한 뒤 다른 말들을 초기화하였습니다.
• 첫 번째 주사위를 진행한 상태에서 search을 이용해서 말이 이동하는 모든 경우를 탐색합니다.
• 모든 경우 탐색 후 얻을 수 있는 최대 점수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 첫 번째 주사위가 지나간 시점에서 말을 놓는 모든 경우를 탐색합니다.
• search함수는 게임이 종료되었을 때 점수가 최대값인지 비교합니다.
• search함수는 외부와 내부를 나누어서 진행하였습니다.

※40칸을 따로 탐색하는 이유는 외부와 내부에서 동시에 도달할 수 있는 칸이기 때문에 해당 칸에 말이 존재하는지 확인을 위해서 따로 탐색을 해주는 것입니다.

 

 

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

public class Main {
    //윷놀이 말의 위치 관련 클래스
    static class position{
        int num;
        boolean inside;
        public position(int num, boolean inside) {
            this.num = num;
            this.inside = inside;
        }
    }
    static int[] input = new int[10];	//윷놀이 주사위 정보
    static boolean[][] check = new boolean[41][2];	//말의 현재 위치 확인 배열
    static ArrayList<position> piece = new ArrayList<>();	//말의 위치 저장 배열
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        for(int i=0;i<10;i++)
            input[i] = Integer.parseInt(st.nextToken());
        //첫 번째 주사위의 값을 첫 번째 말이 이동합니다.
        piece.add(new position(input[0] * 2,false));
        
        //나머지 말 초기화
        for(int i=1;i<4;i++)
            piece.add(new position(0, false));

        search(1, input[0] * 2);	//첫 번째 말 이동한 상태로 모든 경우 탐색
        bw.write(answer + "");	//최대 점수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //첫 번째 말 이동한 환경에서 말의 이동 모든 경우 탐색하는 함수
    static void search(int depth, int value){
        //윷놀이 종료시
        if(depth==10){
            answer = Math.max(answer, value);	//얻은 점수와 최대 점수 비교
            return;
        }
        //말이 이동하는 방법 탐색
        for(int i=0;i<4;i++){
            position cur = piece.get(i);
            if(cur.num>40)	//말이 도착칸에 있을 때
                continue;
            int temp = cur.num;
            if(!cur.inside) {	//외부에 있을 때
                if (cur.num == 10) {		//10칸에 있을 때
                    int next;
                    if (input[depth] <= 3)
                        next = 10 + input[depth] * 3;
                    else
                        next = 25 + (input[depth] - 4) * 5;
                    if (!check[next][1]) {
                        check[10][0] = false;
                        cur.num = next;
                        cur.inside = true;
                        check[next][1] = true;
                        search(depth + 1, value + next);
                        cur.num = temp;
                        cur.inside = false;
                        check[next][1] = false;
                        check[10][0] = true;
                    }
                } else if (cur.num == 20) {		//20칸에 있을 때
                    int next;
                    if (input[depth] <= 2)
                        next = 20 + input[depth] * 2;
                    else
                        next = 25 + (input[depth] - 3) * 5;
                    if (!check[next][1]) {
                        check[20][0] = false;
                        cur.num = next;
                        cur.inside = true;
                        check[next][1] = true;
                        search(depth + 1, value + next);
                        cur.num = temp;
                        cur.inside = false;
                        check[next][1] = false;
                        check[20][0] = true;
                    }
                } else if (cur.num == 30) {		//30칸에 있을 때
                    int next;
                    if (input[depth] <= 3)
                        next = 29 - input[depth];
                    else
                        next = 25 + (input[depth] - 4) * 5;
                    if (!check[next][1]) {
                        check[30][0] = false;
                        cur.num = next;
                        cur.inside = true;
                        check[next][1] = true;
                        search(depth + 1, value + next);
                        cur.num = temp;
                        cur.inside = false;
                        check[next][1] = false;
                        check[30][0] = true;
                    }
                } else {	//10,20,30이 아닌 외부 칸에 있을 때
                    int next = cur.num + 2 * input[depth];
                    if (next > 40) {	//이동하였을 때 도착칸일 때
                        cur.num = 50;
                        check[temp][0] = false;
                        search(depth + 1, value);
                        cur.num = temp;
                        check[temp][0] = true;
                    }else if(next==40){	//이동할 때 40칸일 때
                        if (!check[40][0] && !check[40][1]) {
                            check[temp][0] = false;
                            cur.num = next;
                            check[40][0] = true;
                            check[40][1] = true;
                            search(depth + 1, value + next);
                            cur.num = temp;
                            check[40][0] = false;
                            check[40][1] = false;
                            check[temp][0] = true;
                        }
                    }else {		//그 이외에 칸일 때
                        if (!check[next][0]) {
                            check[temp][0] = false;
                            cur.num = next;
                            check[next][0] = true;
                            search(depth + 1, value + next);
                            cur.num = temp;
                            check[next][0] = false;
                            check[temp][0] = true;
                        }
                    }
                }
            }
            //내부에 있을 때
            else{
                //13~19사이에 있을 때
                if(cur.num>=13 && cur.num<=19){
                    int next = cur.num + 3 * input[depth];
                    if(next > 19)	//19를 벗어나서 25줄로 이동할 때
                        next = 20 + 5 * (input[depth] + (cur.num-19)/3);
                    if(next>40){	//이동한 칸이 도착칸일 때
                        check[cur.num][1] = false;
                        cur.num=50;
                        search(depth+1, value);
                        cur.num = temp;
                        check[cur.num][1] = true;
                    }else if(next==40){	//이동한 칸이 40칸일 때
                        if (!check[40][0] && !check[40][1]) {
                            check[temp][1] = false;
                            cur.num = next;
                            check[40][0] = true;
                            check[40][1] = true;
                            search(depth + 1, value + next);
                            cur.num = temp;
                            check[40][0] = false;
                            check[40][1] = false;
                            check[temp][1] = true;
                        }
                    }else{		//도착칸이 13, 16, 19일 때
                        if(!check[next][1]){
                            check[cur.num][1] = false;
                            cur.num = next;
                            check[next][1] = true;
                            search(depth+1, value + next);
                            cur.num = temp;
                            check[next][1] = false;
                            check[cur.num][1] = true;
                        }
                    }
                }
                //내부 22, 24일 때
                else if(cur.num==22 || cur.num==24){
                    int next = cur.num + 2 * input[depth];
                    if(next > 24)	//22, 24범위에 벗어나 25범위에 들어갈 때
                        next = 20 + 5 * (input[depth] + (cur.num-24)/2);
                    if(next>40){	//이동한 칸이 도착칸일 때
                        check[cur.num][1] = false;
                        cur.num=50;
                        search(depth+1, value);
                        cur.num = temp;
                        check[cur.num][1] = true;
                    } else if(next==40){	//이동한 칸이 40칸일 때
                        if (!check[40][0] && !check[40][1]) {
                            check[temp][1] = false;
                            cur.num = next;
                            check[40][0] = true;
                            check[40][1] = true;
                            search(depth + 1, value + next);
                            cur.num = temp;
                            check[40][0] = false;
                            check[40][1] = false;
                            check[temp][1] = true;
                        }
                    }else{		//도착칸이 22, 24일 때
                        if(!check[next][1]){
                            check[temp][1] = false;
                            cur.num = next;
                            check[next][1] = true;
                            search(depth+1, value + next);
                            cur.num = temp;
                            check[next][1] = false;
                            check[temp][1] = true;
                        }
                    }
                }
                //내부 26, 27, 28일 때
                else if(cur.num>=26 && cur.num<=28){
                    int next = cur.num - input[depth];
                    if(next < 26)	//26, 27, 28범위에 벗어나 25범위에 들어갈 때
                        next = 20 + 5 * (input[depth] - (cur.num-26));
                    if(next>40){	//이동한 칸이 도착칸일 때
                        check[temp][1] = false;
                        cur.num=50;
                        search(depth+1, value);
                        cur.num = temp;
                        check[temp][1] = true;
                    }else if(next==40){		//이동한 칸이 40칸일 때
                        if (!check[40][0] && !check[40][1]) {
                            check[temp][1] = false;
                            cur.num = next;
                            check[40][0] = true;
                            check[40][1] = true;
                            search(depth + 1, value + next);
                            cur.num = temp;
                            check[40][0] = false;
                            check[40][1] = false;
                            check[temp][1] = true;
                        }
                    } else{		//도착칸이 26, 27, 28일 때
                        if(!check[next][1]){
                            check[temp][1] = false;
                            cur.num = next;
                            check[next][1] = true;
                            search(depth+1, value + next);
                            cur.num = temp;
                            check[next][1] = false;
                            check[temp][1] = true;
                        }
                    }
                }
                //25칸 범위일 때
                else{
                    int next = cur.num + 5 * input[depth];
                    if(next>40){		//이동하려는 칸이 도착칸일 때
                        check[cur.num][1] = false;
                        cur.num=50;
                        search(depth+1, value);
                        cur.num = temp;
                        check[cur.num][1] = true;
                    } else if(next==40){		//이동하려는 칸이 40칸일 때
                        if (!check[40][0] && !check[40][1]) {
                            check[temp][1] = false;
                            cur.num = next;
                            check[40][0] = true;
                            check[40][1] = true;
                            search(depth + 1, value + next);
                            cur.num = temp;
                            check[40][0] = false;
                            check[40][1] = false;
                            check[temp][1] = true;
                        }
                    }else{	//도착칸이 30, 35일 때
                        if(!check[next][1]){
                            check[temp][1] = false;
                            cur.num = next;
                            check[next][1] = true;
                            search(depth+1, value + next);
                            cur.num = temp;
                            check[next][1] = false;
                            check[temp][1] = true;
                        }
                    }
                }
            }
        }
    }
}