[ 백준 17825 ] 주사위 윷놀이 ( 자바 )

 [ 백준 17825 ] 주사위 윷놀이 ( java ) 

- 삼성 공채 sw  2019 하반기 기출문제

 

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

 

가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다.

게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에는 그 칸으로 이동할 수 없다. 시작과 도착칸은 말이 이미 있어도 이동할 수 있다. 말이 이동을 마칠때마다 칸에 적혀있는 수가 점수에 추가된다. 

말이 도착으로 이미 이동한 경우에는 더 이상 이동할 수 없고, 말이 이동하려고 하는 칸이 도착을 넘어가는 경우에는 도착에서 이동을 마친다.

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

 

 

 

 

출처: 백준, https://www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

 

 

 

핵심 

지도 나누기 

사람마다 풀이 방법은 다르지만, 여기서는 지도를 경로에 따라 여러 배열로 나누었다. 

어떤 경우의 풀이로는 여러 배열로 나누지 않고, 각 위치마다 index를 부여한 방법도 있었다. 

 

 

방향

파란 칸을 밟을 때, 파란색 화살표로 이동한다. ( 방향만 틀어진 것!! )  그래서, 방향이 틀어지고 말이 더 움직여 가운데 25를 넘어간다면 무조건 위로 올라가는 빨강으로 올라가야 한다. 

 

 

중복을 어떻게 처리할까? 

그림을 여러 배열로 나누었고, 배열에 인덱스가 있다. => 배열과 그 배열의 인덱스로 중복해결!

보통 검은 칸의 경우 중복처리는 간단하다. 하지만, 파란칸(10,20,30)과 25, 40 칸은 주의해야 한다.

왜냐하면 배열을 나누었기 때문. 따라서, 중복 칸의 경우, 메인 라인 (2 4 ~ 40 )이 아닌 분해된 라인위에 올라가게 규칙을 정했다. ( 40은 메인 라인말고 가운데 라인위로 두게 정했음. 하다보면 이게 더 편하다 ) 이 규칙으로 라인이 겹치는 중복칸의 처리를 하나로 통일 시킬 수 있다. 

 

 

배열 이동 

말이 최대 5이동 가능하다. 이 때, 각 배열마다 길이가 달라서 넘어갈 때 주의하기 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
 
public class Main {
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i = 0 ; i < 10 ; i++) {
            dices[i] = Integer.parseInt(st.nextToken());
        }
        
        // 초기화! 
        max = Integer.MIN_VALUE;
        for(int i = 0 ; i < 4; i++) {
            horses[i] = new horse(i);
        }
        
        dfs(0);
        System.out.println(max);
    }
    static int[][] lines = {
            {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40},
            {10, 13, 16, 19},
            {30, 28, 27, 26},
            {20, 22, 24, 25, 30, 35, 40}
    };
    static int[] dices = new int[10];
    
    static int max;
    // moves[i]: i번째 주사위가 나왔을 때, 이동할 말의 index
    static int[] moves = new int[10];
    static void dfs(int pos) {
        
        if(pos == 10) {
            
            // 말 초기화!!
            for(int i = 0 ; i < 4 ; i++) {
                horses[i].l = 0;
                horses[i].pos = 0;
            }
            int score = 0;
            int h_l=0, h_pos;
            for(int i = 0 ; i < 10; i++) {
                boolean ok = horses[moves[i]].move(dices[i]);
                if(ok) {
                    h_l = horses[moves[i]].l;
                    h_pos = horses[moves[i]].pos;
                    // line 3, index(pos) 7을 도착 지점이라고 정했다. 
                    if(h_l == 3 && h_pos == 7)
                        continue;
                    else
                        score += lines[h_l][h_pos];
                }else
                    return ;
            }
            if(max < score) {
                max = score;
            }
            return;
        }
        
        for(int h = 0 ; h < 4 ; h++) {
            moves[pos] = h;
            dfs(pos+1);
        }
    }
    
    static horse[] horses = new horse[4];
    static class horse {
        int l ;
        int pos ;
        int num;
        
        public horse(int num) {
            this.num = num;
            this.l = 0;
            this.pos = 0;
        }
        
        public boolean move(int m) {
            int next = pos + m;
            int nl = l;
            if(l == 0) {
                if(next == 5) {
                    nl = 1;
                    next = 0;
                }else if(next == 10) {
                    nl = 3;
                    next = 0;
                }else if(next == 15) {
                    nl = 2;
                    next = 0;
                }else if(next == 20) {
                    nl = 3;
                    next = 6;
                }else if(next > 20) {
                    nl = 3;
                    next = 7;
                }
            }else if(l == 1) {
                if(next>3) {
                    nl = 3;
                    next--;
                    if(next > 6) {
                        next = 7;
                    }
                }
            }else if(l==2) {
                if(next>3) {
                    nl = 3;
                    next--;
                    if(next > 6) {
                        next = 7;
                    }
                }
            }else if(l == 3) {
                if(next>6) {
                    next = 7;
                }
            }
            
            if(nl == 3 && next == 7) {
                l = nl;
                pos = next;
                return true;
            }
            
            // 중복 처리 
            for(int i = 0 ; i < 4 ; i++) {
                if(num == i)
                    continue;
                if(horses[i].l == 3 && horses[i].pos == 7)
                    continue;
                if(horses[i].l == 0 && horses[i].pos == 0)
                    continue;
                
                if(horses[i].l == nl && horses[i].pos == next ) {
                    return false;
                }
            }
            l = nl;
            pos = next;
            return true;
        }
    }
}