주사위 윷놀이

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2885 1052 652 31.976%

문제

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

img

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

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

입력

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

출력

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

풀이

글쎄,? 어떻게 풀어야 할까

일단, 예상 로직은 다음과 같다.

  • 그림이 그래프 형태를 이루고 있고, 얻을 수 있는 점수의 최댓값
  • 말을 골라서 이동시켜야 함.
  • Dfs + 백트래킹을 사용하면 될 것 같다.

하지만, 고려할 점

  • 그림을 어떻게 표현할 것인가?
  • 말을 선택하는 부분!
  • 이동 전에 이동할 칸에 말이 있는지 여부를 확인해야 한다.

buddev 님의 블로그를 참고했다.

구현 포인트

파란 점일 때, 아닐 때를 구분해서 리스트를 구현해주면 된다.

1
2
3
4
5
6
7
8
9
10
11
static class Node {
int score; // 해당 칸의 점수.
int red; // 빨간 화살표로 이동할 경우, 다음 점.
int blue; // 파란 화살표로 이동할 경우, 다음 점.
boolean isBlue; // 파란 점인지 여부.

Node(int score, int red) {
this.score = score;
this.red = red;
}
}

문제에서 칸의 번호와 점수가 동일한데, 같은 번호가 있는 칸이 두개씩 있는 경우가 존재한다.
따라서 겹치는 번호들에 한해서 번호를 바꿔서 지정했다.

이를 디버깅하고 난 후, 내가 생각한 풀이를 적는다.

  1. 윷놀이 판의 가장 바깥 라인은 2의 배수로 채운다. -> 문제와 똑같이 간다.
  2. 꺾이는 부분, 파란 점으로 인한 지름길이다. 바깥 라인과 값이 중복되기 때문에 다른 값으로 대체한다.
  3. 중복을 허용하는 수열을 이용해서 주사위가 나오는 값 별로 올 수 있는 말의 경우를 모두 구한다.
  4. 모두 구했으면, now 배열, check 배열을 초기화 하고 말을 움직인다.(move() 호출)

[Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* created by victory_woo on 2020/04/15
*/
public class sw17825Re {
private static final int TEN = 10;
private static int[] permutation, now, step;
private static boolean[] check;
private static Node[] map;
private static int max;

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

permutation = new int[TEN];
step = new int[TEN];
map = new Node[43];

for (int i = 0; i < TEN; i++) step[i] = toInt(in[i]);
setDice();
getPermutation(0);
System.out.println(max);
}

// 파란 점이 있는 부분에 대해서 처리한다.
// 바깥 라인과의 중복된 값이 존재하기 때문에 인덱스를 다르게 주었고, 값은 그대로 저장했다.
// 또한, 빨간 점으로 된 다음 좌표를 저장한다.
private static void setDice() {
for (int i = 0; i <= 40; i += 2) map[i] = new Node(i, i + 2);

map[10].isBlue = map[20].isBlue = map[30].isBlue = true;

map[10].setBlue(11);
map[20].setBlue(17);
map[30].setBlue(31);

map[11] = new Node(13, 13);
map[13] = new Node(16, 15);
map[15] = new Node(19, 25);

map[17] = new Node(22, 19);
map[19] = new Node(24, 25);

map[31] = new Node(28, 33);
map[33] = new Node(27, 35);
map[35] = new Node(26, 25);

map[25] = new Node(25, 37);

map[37] = new Node(30, 39);
map[39] = new Node(35, 40);

map[42] = new Node(0, 42);
}

private static void getPermutation(int depth) {
if (depth == 10) {
now = new int[4];
check = new boolean[43];
move();
return;
}

for (int i = 0; i < 4; i++) {
permutation[depth] = i;
getPermutation(depth + 1);
}
}

private static void move() {
int score = 0;
for (int i = 0; i < TEN; i++) {
// 말을 움직여서 말이 도착한 지점의 값을 구한다.
// 말이 step 만큼 움직이도록 horseMove() 함수를 호출한다.
// end 값은 말이 주사위 step 만큼 움직이고 난 뒤의 칸.
int end = horseMove(permutation[i], step[i]);
if (end == -1) return;
now[permutation[i]] = end; // 현재 말이 있는 칸을 업데이트 한다.
score += map[end].score;
}

if (max < score) max = score;
}

// now : 윷놀이 판 위에서 말이 위치한 인덱스.(말이 있는 윷놀이 판의 인덱스)
private static int horseMove(int horse, int step) {
// 몇 번째 말이 움직일 것인지 뽑는다.
// 즉, 이동할 말을 정한다.
int temp = now[horse];

// 말이 step 만큼 움직인다.
// 첫 좌표이면서 파란 점이라면 파란 점을 temp 에 저장한다.
// 그게 아니라면 말이 이동할 다음 좌표(빨간 점의 위치)를 찾아 temp 에 저장한다.
for (int i = 0; i < step; i++) {
if (i == 0 && map[temp].isBlue) {
temp = map[temp].blue;
continue;
}

temp = map[temp].red;
}

// 도착 지점에 도착하지도 않았는데, 방문한 곳을 또 방문한 경우.
if (temp <= 40 && check[temp]) {
return -1;
} else {
check[now[horse]] = false;
check[temp] = true;
return temp;
}
}

private static int toInt(String value) {
return Integer.parseInt(value);
}

static class Node {
int score;
int blue;
int red;
boolean isBlue;

public Node(int score, int red) {
this.score = score;
this.red = red;
}

public void setBlue(int blue) {
this.blue = blue;
}

public void setRed(int red) {
this.red = red;
}

}
}

이 문제는 주사위를 저렇게 구현해 낼 수 있느냐 없느냐의 싸움인 것 같다.
풀고나면 어렵지 않지만, 저렇게 생각해 내는 연습이 필요한 것 같다.
더 열심히 하자~
뿅!