주사위 윷놀이 (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();
}
}
Author And Source
이 문제에 관하여(주사위 윷놀이 (17825)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@front/백준-주사위-윷놀이-17825저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)