백준 - 주사위 윷놀이 (17825)

1. 문제

문제 링크

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

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

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

입력

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

출력

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

2. 풀이

재귀적으로 말을 선택하는 모든 경우의 수를 만들어서 최댓값을 구하는 문제입니다.

계획1 - 윷놀이 게임판의 규칙을 테이블로 정의합니다.

// 0번째 idx -> 그 자리에서 얻는 점수, 1~5 주사위가 나왔을 때 가야할 idx
static final int[][] rule = {
		{0,1,2,3,4,5},
		{2,2,3,4,5,9},
		{4,3,4,5,9,10},
		{6,4,5,9,10,11},
		{8,5,9,10,11,12},
		{10,6,7,8,21,22},
		{13,7,8,21,22,23},
		{16,8,21,22,23,31},
		{19,21,22,23,31,32},
		{12,10,11,12,13,14},
		{14,11,12,13,14,15},
		{16,12,13,14,15,16},
		{18,13,14,15,16,17},
		{20,19,20,21,22,23},
		{22,15,16,17,18,27},
		{24,16,17,18,27,28},
		{26,17,18,27,28,29},
		{28,18,27,28,29,30},
		{30,24,25,26,21,22},
		{22,20,21,22,23,31},
		{24,21,22,23,31,32},
		{25,22,23,31,32,32},
		{30,23,31,32,32,32},
		{35,31,32,32,32,32},
		{28,25,26,21,22,23},
		{27,26,21,22,23,31},
		{26,21,22,23,31,32},
		{32,28,29,30,31,32},
		{34,29,30,31,32,32},
		{36,30,31,32,32,32},
		{38,31,32,32,32,32},
		{40,32,32,32,32,32},
		{0,32,32,32,32,32},
};

문제에서 나온 주사위 게임판을 1차원 배열로 단순화 시켜서 생각을 해봅시다.
각 칸들에 대해서 현재 위치에서 얻는 점수와 주사위 값에 따라 이동하는 위치를
테이블로 정의가 가능해집니다.

이런식으로 말이죠.

계획2 - 완전 탐색을 구현합니다.

테이블 정의했으니 완전 탐색은 껌이죠.
전체 코드로 확인합니다.

3. 전체 코드

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	// 0번째 idx -> 그 자리에서 얻는 점수, 1~5 주사위가 나왔을 때 가야할 idx
	static final int[][] rule = {
			{0,1,2,3,4,5},
			{2,2,3,4,5,9},
			{4,3,4,5,9,10},
			{6,4,5,9,10,11},
			{8,5,9,10,11,12},
			{10,6,7,8,21,22},
			{13,7,8,21,22,23},
			{16,8,21,22,23,31},
			{19,21,22,23,31,32},
			{12,10,11,12,13,14},
			{14,11,12,13,14,15},
			{16,12,13,14,15,16},
			{18,13,14,15,16,17},
			{20,19,20,21,22,23},
			{22,15,16,17,18,27},
			{24,16,17,18,27,28},
			{26,17,18,27,28,29},
			{28,18,27,28,29,30},
			{30,24,25,26,21,22},
			{22,20,21,22,23,31},
			{24,21,22,23,31,32},
			{25,22,23,31,32,32},
			{30,23,31,32,32,32},
			{35,31,32,32,32,32},
			{28,25,26,21,22,23},
			{27,26,21,22,23,31},
			{26,21,22,23,31,32},
			{32,28,29,30,31,32},
			{34,29,30,31,32,32},
			{36,30,31,32,32,32},
			{38,31,32,32,32,32},
			{40,32,32,32,32,32},
			{0,32,32,32,32,32},
	};
	static final int TURN_COUNT = 10; // 전체 턴은 10번
	static final int HORSE = 4; // 말의 개수는 4개
	static final int DESTINATION = 32; // 도착칸은 32번
	static int diceValues[] = new int[TURN_COUNT]; // 주사위 값을 저장하는 배열
	static int pos[] = new int[HORSE]; // 말들의 위치를 저장하는 배열
	static boolean[] locate = new boolean[33]; // 말들의 위치를 저장하는 배열
	
	static int max(int turn, int score) {
		if (turn == TURN_COUNT) return score;
		
		int ret = -1;
		
		for (int i = 0; i < HORSE; i++) {
			// 현재 말의 정보
			int[] v = rule[pos[i]];
			
			// 현재 나온 주사위
			int diceValue = diceValues[turn];
			
			// 다음 위치
			int nextPos = v[diceValue];
			
			// 현재 말이 도착했거나, 도착칸이 아니면서 이동하려는 칸에 말이 있다면
			if (pos[i] == DESTINATION || (nextPos != DESTINATION && locate[nextPos])) continue;
			
			// 현재 위치 저장
			int curPos = pos[i];
			
			// 이동
			locate[curPos] = false; // 현재 있던 곳 false
			locate[nextPos] = true; // 이동하는 곳 true
			pos[i] = nextPos; // 위치 갱신
			ret = Math.max(ret, max(turn + 1, score + rule[nextPos][0])); // 다음 위치의 점수를 더해준다
			pos[i] = curPos; // 위치 되돌리기 (백트래킹)
			locate[nextPos] = false; // 이동했던 곳  false
			locate[curPos] = true; // 현재있는 곳 true
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < TURN_COUNT; i++) {
			diceValues[i] = Integer.parseInt(stk.nextToken());
		}
		
		bw.write(max(0, 0) + "");
		bw.close();
	}
}