[백준] 17825번 - 주사위 윷놀이

문제 >

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

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

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

 

입력 >

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

 

출력 >

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

 

해결방법 > 

DFS(깊이우선탐색)알고리즘으로 문제를 해결했다.

 

일단은 문제에 주어진 판을 아래와 같이 다시 만들었다.

 

각 노드마다 번호를 매기고, 문제에서 주어진 숫자는 간선의 가중치로 생각하는 방법이다.

 

따라서 33 X 33 크기의 인접행렬을 만들고 간선의 가중치를 저장했다.

 

지도 정보를 만들었다면 이제 최대값을 찾아야하는데 두 가지 과정이 필요했다.

 

1) 깊이 우선 탐색을 통해 말이 움직이는 순서의 모든 경우의 수를 찾는다.

 

2) 각 경우마다 깊이 우선 탐색을 사용해서 주사위의 숫자만큼 이동한다.

 

각 과정을 자세히 살펴보면

 

 

1) 깊이 우선 탐색을 통해 말이 움직이는 순서의 모든 경우의 수를 찾는다.

 

1)번 과정 같은 경우는 주사위 숫자 10개에 따라 4개의 말을 선택할 수 있기 때문에 중복을 허용하는 순열과 같다.

 

경우의 수는 4^10으로 연산 수가 크다.

 

2)번 과정에서도 깊이우선탐색을 해야하는데 접근 방식이 잘못되었는가 생각을 많이 했지만 백트레킹으로 해결할 수 있었다.

 

 

2) 각 경우마다 깊이 우선 탐색을 사용해서 주사위의 숫자만큼 이동한다.

 

2)번 과정은 선택된 말로 i번째 주사위 수만큼 움직이는 것이다. 다시말해 주사위 수만큼 인접한 노드로 깊이있게 방문한다.

 

이 부분을 깊이우선탐색으로 해결한 이유 인접한 노드가 순서대로 있지않고,

 

5, 10, 15번째 노드, 즉 경로가 두 갈래로 나뉘는 노드가 있기  때문이다.

 

노드가 두 갈래로 나뉜다는 말은 간선의 정보가 두 개가 존재한다는 것인데, 두 가지 조건으로 해결할 수 있다

 

a) 탐색을 시작한 노드가 두 갈래로 나뉘는 노드라면, 노드 값이 큰 노드를 방문한다.

게임판에 대한 정보를 새로 만들 때, 두 갈래에서 우선으로 방문해야 하는 노드의 원소 값을 크게 만들었기 때문에 가능하다.

 

b) 탐색 중간에 방문한 노드가 두 갈래로 나뉘는 노드라면, 노드 값이 작은 노드를 방문한다.

 

 

지금까지 말한 부분만 구현한다면 연산 시간이 오래 걸린다. 따라서 1)번 과정의 백트레킹할 조건을 만들어준다. 조건은 아래와 같다.

 

a) 주사위 수만큼 이동했을 때, 다른 말이 존재한다면 경우(문제에서 요구한 조건)

 

b) 현재까지 이동한 간선의 합이 최대값이 될 가능성이 없을 경우

 

c) 도착지점에 도착한 말을 움직이려하는 경우

 

 

이 문제는 조금 억지로 풀었다는 느낌을 많이 받았다. 코드를 작성하는 내내 DFS를 중첩해서 사용하니까 연산시간에 대한

 

압박감도 많이 받았고, 이렇게 구현하는게 맞는가하는 생각도 많이 들었다.

 

처음 제출했을 때 연산 시간이 너무 커서 백트레킹 조건도 덕지덕지 붙여넣은 느낌이다.

 

다시 생각해봐야할 문제인 것 같다.

 

[JAVA]

package baekjoon;

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

public class BOJ_17825_2 {
	static int[] dice = new int[10];
	static int[][] map = new int[33][33];
	static int next = 0;
	static int weight = 0;
	static int max = 0;
	
	public static class Node implements Comparable<Node>{
		int v;
		int w;
		
		Node(int v, int w) {
			this.v = v;
			this.w = w;
		}
		
		@Override
		public int compareTo(Node n) {
			if(this.v < n.v) return 1;
			else return -1;
		}
	}
	
	public static void set() {
		for(int i = 0; i < 20; i++) {
			map[i][i + 1] = 2 * (i + 1);
		}
		map[5][21] = 13; map[21][22] = 16; map[22][23] = 19; map[23][24] = 25;
		
		map[15][27] = 28; map[27][26] = 27; map[26][25] = 26; map[25][24] = 25;
		
		map[10][28] = 22; map[28][29] = 24; map[29][24] = 25;
		
		map[24][30] = 30; map[30][31] = 35; map[31][20] = 40;
		
		map[20][32] = 1;
	}
	
	public static void move(int cnt, int start) {
		if(cnt == 0) return;
		if(next == 32) {
			weight = 1;
			return;
		}
		ArrayList<Node> l = new ArrayList<>();
		for(int i = 0; i < 33; i++) {
			if(map[next][i] != 0) {
				l.add(new Node(i, map[next][i]));
			}
		}
		
		if(l.size() == 1) {
			next = l.get(0).v;
			weight = l.get(0).w;
		}
		
		else if(l.size() > 1) {
			Collections.sort(l);
			if(next == start) {
				next = l.get(0).v;
				weight = l.get(0).w;
			}
			else {
				next = l.get(1).v;
				weight = l.get(1).w;
			}
		}
		move(cnt-1, start);
	}
	
	public static void select(int h, int[] ph, int x, int sum) {
		if(x == 10) {
			for(int i = 0; i < 4; i++) {
				if(ph[i] == 32) sum--;
			}
			max = Math.max(max, sum);
			return;
		}
		if(ph[h] == 32) return;
		
		int[] horse = ph.clone();
		next = horse[h];
		move(dice[x], next);
		
		for(int i = 0; i < 4; i++) {
			if(next != 32 && horse[i] == next) return; 
		}
		horse[h] = next;
		sum += weight;
		
		if(sum + (9 - x) * 40 < max) return;
		
		for(int i = 0; i < 4; i++) {
			select(i, horse, x + 1, sum);
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());
		for(int i = 0; i < 10; i++) {
			dice[i] = Integer.parseInt(tk.nextToken());
		}
		
		set();
		for(int i = 0; i < 4; i++) {
			int[] horse = new int[4];
			select(i, horse, 0, 0);
		}
		System.out.println(max);
	}
}