[백준 17825] 주사위 윷놀이 - JAVA

주사위 윷놀이

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	6805	2586	1501	34.160%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

xxxxxxxxxx
1 2 3 4 1 2 3 4 1 2

예제 출력 1 복사

xxxxxxxxxx
190

예제 입력 2 복사

xxxxxxxxxx
1 1 1 1 1 1 1 1 1 1

예제 출력 2 복사

xxxxxxxxxx
133

예제 입력 3 복사

xxxxxxxxxx
5 1 2 3 4 5 5 3 2 4

예제 출력 3 복사

xxxxxxxxxx
214

예제 입력 4 복사

xxxxxxxxxx
5 5 5 5 5 5 5 5 5 5

예제 출력 4 복사

xxxxxxxxxx
130

 

 

풀이

19년도 삼성전자 코딩테스트 기출문제.

 

문제를 보고 추가적인 제한조건을 생각해야 하는게 까다로운 문제였습니다.

 

이 문제의 핵심인 빨간색으로 이동하는 경우와 파란색으로 이동하는 경우가 처리해줘야할 핵심 로직입니다.

 

이렇게 윷놀이 판이 있을 경우 파란색 원으로 되어있는

10, 20, 30 이 써져있는 원의 경우 두가지 길이 있습니다.

 

파란색 길과 (13) 빨간색 길(12)가 있습니다.

만약 주사위를 던진 수가 딱 파란색 원에 도착한다면 이어서 주사위를 던질때 파란색 길로 가야하는건 문제를 보신 분이라면 다 알 것입니다.

 

위의 그림에서 동그라미 안에 있는 숫자는 인덱스가아닌 값 입니다.

그러면 위의 그림을 인덱스로 다시 표현하면 아래와 같습니다

(제가 임의로 붙인 인덱스이며 꼭 이렇게 안해도 됩니다)

 

 

 

이제 위의 그림을 이용해서 연결관계를 만들어 봅시다.

 

class Node{
    int red_next, blue_next,now_num;
    
    Node(int red_next, int blue_next, int now_num){
        this.red_next = red_next;
        this.blue_next = blue_next;
        this.now_num = now_num;
    }
}

 

위 윷놀이 판의 동그라미 원은 총 31칸이네요

31칸의 Node타입의 배열을 만들어주면 됩니다.

 

red_next는 빨간색 길로 갔을 때의 다음 원의 "인덱스" 입니다.

blue_next는 파란색 길로 갔을 때의 다음 원의 "인덱스" 입니다.

now_num은 현재 인덱스 원안에 있는 값 입니다. 원본 그림에 써져있는 2,4,6,8,10 등 써져있는 값입니다.

 

그리고 연결관계를 인덱스를 붙힌 그림과 원본 그림에 있는 값을 하나하나 적어주면 됩니다.

blue_next가 없는 경우는 0으로 값을 뒀습니다.

 

x
    public static void init() {
        
        map[0] = new Node(1,0,0);
        
        int map_num = 2;
        for(int i=1; i<=19; i++) {
            map[i] = new Node(i+1,0,map_num);
            map_num+=2;
        }
        map[20] = new Node(100,0,40);       // 100은 도착점이라 가정
        
        
        map[5].blue_next = 21;
        map[10].blue_next = 29;
        map[15].blue_next = 27;
        
        map[21] = new Node(22,0,13);
        map[22] = new Node(23,0,16);
        map[23] = new Node(24,0,19);
        map[24] = new Node(30,0,25);
        map[25] = new Node(24,0,26);
        map[26] = new Node(25,0,27);
        map[27] = new Node(26,0,28);
        map[28] = new Node(24,0,24);
        map[29] = new Node(28,0,22);
        map[30] = new Node(31,0,30);
        map[31] = new Node(20,0,35);
        
        horse = new Horse[5];
        
        // 아래에서 설명
        for(int i=1; i<=4; i++) {
            horse[i] = new Horse(0,false);
        }   
    }

 

그 다음 4개의 말은 현재 인덱스의 위치와 boolean 변수 flag를 두었는데요

 

class Horse{
    int idx;
    boolean flag;
    Horse(int idx, boolean flag){
        this.idx= idx;
        this.flag=  flag;
    }
}

flag가 true이면 파란색으로 칠해진 것으로 가는겁니다.

문제에서 5번째 인덱스 , 10번째 인덱스, 15번째 인덱스의 경우 파란색으로 빠질수 있으니 주사위를 굴려 최종적으로 도착한 위치가

5, 10, 15인덱스에 도착한다면 flag = true로 둡니다.

 

아래 로직에서 flag가 true이면 Node클래스의 blue_next로 이동하면 됩니다.

 

 

그 다음 4개의 말을 이동할 것을 정해줘야 하는데, 이는 순열로 정할수 있습니다

주사위의 횟수만큼 순열을 통해 값을 만들어줍니다

주사위를 4번 돌려서 1111이 나오면 1번말을 4번 주사위 던지는 것인데

순열을 구하면

1111 ~ 4444의 모든 경우의 수가 나오기 때문에 가능합니다.

 

 

그리고 문제의 조건중에서 중복된 말에 대한 부분이 있는데

중복된 칸에 도착을 한다면 아예 갈 수 없다고 처리를 하고 해줘야 합니다.

 

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int dfs_horse[] = new int[11];
    static Node map[];
    static Horse horse[];
    static int dice[] = new int[11];
    static int ans = 0;
    static int tmp_ans = 0;
    static boolean visited[] = new boolean [32];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        map = new Node[32];
        init();
        
        String [] t = br.readLine().split(" ");
        
        for(int i=1; i<=10; i++) {
            dice[i] = Integer.parseInt(t[i-1]);
        }
​
        dfs(1);
​
        System.out.println(ans);
    }
    public static boolean go(int dice, int horse_num) {
        
        Horse a = horse[horse_num];
        int now_pos = a.idx;    // 현재 말이 있는 위치
        boolean flag = a.flag;      
        
        if(now_pos==100) {  // 밖으로 나간 말
            return true;            
        }
        
        
        for(int i=0; i<dice; i++) {     // 주사위의 칸 만큼 이동
            
            if(now_pos ==100) {
                horse[horse_num] = new Horse(now_pos,flag);
                visited[a.idx] = false;
                return true;
            }
            
            
            if(now_pos ==5 || now_pos ==10 || now_pos ==15) {
                if(flag) {
                    now_pos = map[now_pos].blue_next;
                }
                else {
                    now_pos = map[now_pos].red_next;
                }
            }
            else {
                now_pos = map[now_pos].red_next;
            }
        }
        
        if(now_pos ==100) {
            horse[horse_num] = new Horse(now_pos,flag);
            visited[a.idx] = false;
            return true;
        }
        
        
        // 말이 주사위 칸 만큼 다 이동했고 갈림길에 있는 경우
        if(now_pos ==5 || now_pos ==10 || now_pos ==15) {
            flag = true;
        }
        
        if(visited[now_pos]) {
​
            return false;
        }
        tmp_ans +=map[now_pos].now_num;
        horse[horse_num] = new Horse(now_pos,flag); // 말의 위치 바꿔줌
        visited[a.idx] = false;
        visited[now_pos] = true;
        
        return true;
    }
    public static void dfs(int level) {
        if(level==11) {
            tmp_ans = 0;
            for(int i=1; i<=10; i++) {
                if(!go(dice[i],dfs_horse[i])) {
                    clear();
                    return ;
                }
​
            }
            ans = Math.max(ans, tmp_ans);
            clear();
            return ;
        }
        
        for(int i=1; i<=4; i++) {
            dfs_horse[level] = i;
            dfs(level+1);
        }
    }
    public static void clear() {
        // 말의 위치정보 초기화
        for(int i=1; i<=4; i++) {
            horse[i] = new Horse(0,false);
        }
        
        // 중복을 위한 방문정보 초기화
        visited = new boolean [32];
    }
    public static void init() {
        
        map[0] = new Node(1,0,0);
        
        int map_num = 2;
        for(int i=1; i<=19; i++) {
            map[i] = new Node(i+1,0,map_num);
            map_num+=2;
        }
        map[20] = new Node(100,0,40);       // 100은 끝이라 가정
        
        
        map[5].blue_next = 21;
        map[10].blue_next = 29;
        map[15].blue_next = 27;
        
        map[21] = new Node(22,0,13);
        map[22] = new Node(23,0,16);
        map[23] = new Node(24,0,19);
        map[24] = new Node(30,0,25);
        map[25] = new Node(24,0,26);
        map[26] = new Node(25,0,27);
        map[27] = new Node(26,0,28);
        map[28] = new Node(24,0,24);
        map[29] = new Node(28,0,22);
        map[30] = new Node(31,0,30);
        map[31] = new Node(20,0,35);
        
        horse = new Horse[5];
        
        for(int i=1; i<=4; i++) {
            horse[i] = new Horse(0,false);
        }   
    }
}
class Node{
    int red_next, blue_next,now_num;
    
    Node(int red_next, int blue_next, int now_num){
        this.red_next = red_next;
        this.blue_next = blue_next;
        this.now_num = now_num;
    }
}
class Horse{
    int idx;
    boolean flag;
    Horse(int idx, boolean flag){
        this.idx= idx;
        this.flag=  flag;
    }
}
​