문제
주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.
- 처음에는 시작 칸에 말 4개가 있다.
- 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
- 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
- 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
- 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.
주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.
입력
첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.
출력
얻을 수 있는 점수의 최댓값을 출력한다.
풀이
턴 수가 정확히 10번이고 매번 선택 가능한 말이 최대 4개이므로, 모든 선택을 백트래킹으로 탐색할 수 있다. 핵심은 복잡한 게임판을 어떻게 상태로 표현하느냐다.
코드에서는 각 칸을 번호로 압축해서 score[], nextNode[], blueNode[]로 게임판을 표현한다. 일반 이동은 nextNode를 따라가고, 파란 칸에서 출발할 때만 첫 한 걸음을 blueNode로 바꾸면 된다.
또한 서로 다른 경로가 중간에 합쳐지는 칸들이 있기 때문에, 실제 좌표가 아니라 "같은 칸이면 같은 번호"가 되도록 맵을 구성하는 것이 중요하다. 그렇게 해 두면 visited[] 하나로 말 충돌 여부를 바로 검사할 수 있다.
이후 play(turn, curScore)에서 매 턴마다 4개의 말 중 하나를 골라 이동시키고, 도착 칸이 아니면서 이미 다른 말이 있는 칸이면 그 선택은 버린다. 10턴까지 모두 진행했을 때 점수 최댓값을 갱신하면 된다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int[] dices = new int[10];
static int[] piece = new int[4];
static boolean[] visited = new boolean[33];
static int[] score = new int[33];
static int[] nextNode = new int[33];
static int[] blueNode = new int[33];
static int maxScore = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
setupMap();
for (int i = 0; i < 10; i++)
dices[i] = Integer.parseInt(st.nextToken());
play(0, 0);
System.out.println(maxScore);
}
static void setupMap() {
// 일반 루트
for (int i = 0; i <= 20; i++) {
score[i] = 2 * i;
nextNode[i] = i + 1;
}
// 도착 노드
score[21] = 0;
nextNode[21] = 21;
// 파랑 루트 →
blueNode[5] = 22; score[22] = 13;
nextNode[22] = 23; score[23] = 16;
nextNode[23] = 24; score[24] = 19;
nextNode[24] = 25;
// 파랑 루트 ↑
blueNode[10] = 26; score[26] = 22;
nextNode[26] = 27; score[27] = 24;
nextNode[27] = 25;
// 파랑 루트 ←
blueNode[15] = 28; score[28] = 28;
nextNode[28] = 29; score[29] = 27;
nextNode[29] = 30; score[30] = 26;
nextNode[30] = 25;
// 파랑 공통 루트
nextNode[25] = 31; score[31] = 30;
nextNode[31] = 32; score[32] = 35;
nextNode[32] = 20;
score[25] = 25;
}
static void play(int turn, int curScore) {
if (turn == 10) {
maxScore = Math.max(maxScore, curScore);
return;
}
for (int i = 0; i < 4; i++) {
int curPosition = piece[i];
// 이미 도착한 말
if (curPosition == 21)
continue;
int move = dices[turn];
int nextPosition = curPosition;
// 파랑 루트 확인
if (blueNode[curPosition] != 0) {
nextPosition = blueNode[curPosition];
move--;
}
// 루트 이동
while (move > 0) {
nextPosition = nextNode[nextPosition];
if (nextPosition == 21) break;
move--;
}
if (visited[nextPosition] && nextPosition != 21)
continue;
visited[curPosition] = false;
visited[nextPosition] = true;
piece[i] = nextPosition;
play(turn + 1, curScore + score[nextPosition]);
visited[curPosition] = true;
visited[nextPosition] = false;
piece[i] = curPosition;
}
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
이 문제는 완전탐색 자체보다 게임판을 얼마나 정확하게 모델링하느냐가 더 중요하다. 칸 번호를 잘 압축해 두면, 복잡해 보이는 윷놀이도 백트래킹으로 밀어붙일 수 있다.
