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

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

17825번: 주사위 윷놀이

 

풀이 방법

구현 문제이며 DFS + 백트래킹을 사용하여 구현하였다.

1. 시작 칸은 1, 도착 칸은 41로 설정하였다.
2. 1~4번의 말은 Map 에 key: 번호, value: [pos, blue] 를 저장하여 관리하도록 한다.
   • pos: 현재 말의 위치
   • blue: 파란색 화살표를 지나온 경로인지 여부, 지나온 경로라면 1
3. 각 칸에 있는 말의 번호를 기록하기 위해 2차원 배열 board 를 선언하였다.
   • 다른 경로 중 숫자가 겹치는 칸이 있으므로 두 가지로 구분하여 말의 번호를 저장해야 한다. 
   • board[i][0] : 빨간색 화살표만 따라온 경로의 i번 칸
   • board[i][1] : 파란색 화살표를 지나온 경로의 i번 칸
4. 첫번째 턴부터 dfs 함수를 호출하여 1번 말부터 주사위에서 나온 수만큼 이동시켜본다.
   • 현재 칸이 파란색 칸 10, 20, 30이면 알맞게 다음 칸으로 이동시킨 후 blue를 1로 바꾼다.
   • 남은 이동 수만큼 한 칸씩 이동시킨다.
     • 현재 칸이 40이면 그 다음 칸이 도착 칸이므로 pos 를 41로 바꾸고 바로 탈출한다.
     • pos = 1이면 시작 칸이므로 2로 간다.
     • blue 가 1인 경우, 즉 파란색 화살표를 지난 경로인 경우 현재 경로에 따라 알맞게 이동한다.
     • blue 가 0인 경우, 즉 빨간색 화살표만 지나는 경우엔 pos+2 의 위치로 이동시킨다.
5. 이동을 마친 칸이 도착 칸이라면 이동은 하되 점수는 획득하지 않는다.
6. 도착 칸이 아니면 board[pos][blue] 가 0인지, 즉 말이 없는지 확인하고 없다면 이동한 후 점수를 획득한다.
7. 단, 40에선 두 경로가 합쳐지는 곳이므로 꼭 board[40][0] 와 board[40][1] 이 모두 0인지를 확인한다.
8. 말을 이동시킨 뒤엔 현재까지 점수 총합에 획득한 점수를 더하여 dfs 함수에 넘겨 재귀호출한다.
9. 재귀호출이 끝나면 이전 상태로 복구하여 그 다음 번호의 말을 이동시키는 것을 반복한다.

 

코드

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

public class Main {

    static int[] arr = new int[10];
    static int[][] board = new int[42][2];
    static int maxScore = Integer.MIN_VALUE;
    static Map<Integer, int[]> mals = new HashMap<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");

        for(int i=0; i<10; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }

        // 4개의 말 위치 저장
        for(int i=1; i<=4; i++) {
            mals.put(i, new int[]{1, 0}); // 현재 위치와 파란색 화살표를 지난 경로인지 여부 삽입
        }
        dfs(0, 0);
        System.out.println(maxScore);
    }

    public static void dfs(int turn, int totalScore) {
        // 10번의 턴을 마침
        if(turn == 10) {
            maxScore = Math.max(totalScore, maxScore);
            return;
        }

        int[][] tmp = new int[42][2];
        for(int i=1; i<=41; i++) {
            tmp[i][0] = board[i][0];
            tmp[i][1] = board[i][1];
        }

        for(int mal=1; mal<=4; mal++) {
            int[] curPos = mals.get(mal);
            int cur = curPos[0];
            int blue = curPos[1];

            if (cur != 41) { // 도착한 말이 아니면
                int score = move(mal, arr[turn]);
                if(score > 0) { // 이동 가능
                    // 도착 칸이면 점수 포함 x
                    if(score == 41) {
                        score = 0;
                    }
                    dfs(turn+1, totalScore + score);
                    // 원 상태로 복구
                    mals.put(mal, new int[]{cur, blue});
                    for (int i=1; i<=41; i++) {
                        board[i][0] = tmp[i][0];
                        board[i][1] = tmp[i][1];
                    }
                }
            }
        }
    }

    public static int move(int mal, int step) {
        int[] curPos = mals.get(mal);
        int pos = curPos[0];
        int blue = curPos[1];
        // 파란색 칸에서 출발이라면
        if(blue == 0 && (pos % 10 == 0 && pos < 40)) {
            if(pos == 10) {
                pos += 3;
            } else if(pos == 20) {
                pos += 2;
            } else if(pos == 30) {
                pos -= 2;
            }
            step--;
            blue = 1; // 파란색 경로를 지남
        }

        for(int i=0; i<step; i++) {
            // 도착 칸으로 이동한 경우
            if(pos == 40) {
                pos = 41;
                break;

            } else if(pos == 1) { // 시작 칸이면
                pos = 2;
                continue;
            }

            if(blue == 1) { // 파란색 화살표를 지나온 경로인 경우
                if(pos % 5 == 0) {
                    pos += 5;
                } else if(pos == 19 || pos == 26 || pos == 24) {
                    pos = 25;
                } else if(pos > 25){
                    pos -= 1;
                } else if(pos > 20) {
                    pos += 2;
                } else {
                    pos += 3;
                }

            } else { // 빨간색만 따라가는 경우
                pos += 2;
            }
        }
        // 말을 고를 수 있는지 확인
        if(pos == 40) {
            if(board[pos][0] == 0 && board[pos][1] == 0) { // 40인 경우엔 두 경로가 합쳐지므로 둘 다 확인
                board[curPos[0]][curPos[1]] = 0;
                board[pos][blue] = mal;
                mals.put(mal, new int[]{pos, blue});
                return pos; // 점수
            }

        } else if(pos == 41 || board[pos][blue] == 0) { // 도착했거나 이동을 마치는 칸에 말이 없으면
            board[curPos[0]][curPos[1]] = 0;
            board[pos][blue] = mal;
            mals.put(mal, new int[]{pos, blue});
            return pos;

        }
        return 0; // 이동 불가
    }
}