[백준] 17825 주사위 윷놀이

---

이동할 수 있는 말에 대한 경우의 수를 백트래킹 알고리즘으로 구해 해결할 수 있다.

 

유의 해야 할 부분은 윷판에 지름길이 존재한다는 것이다. 나는 지름길을 처리하기 위해서 루트를 0 - 4로 나누었다.

route0에서 처리

route0에서 고려해야할 것은 5, 10, 15 번에서 출발할 경우 지름길을 통하는 것이다. 5는 1번루트, 10은 2번루트 마지막으로 15는 3번 루트로 변경한다. 그리고 이동 해야 할 거리는 주사위의 숫자 크기를 따른다.

 

그리고 route0에서 말이 이동할 때 19 번을 넘을 겅우 route4로 루트를 변경 해야 한다. 이떄 route0의 길이를 오프셋으로 하고 이동 해야할 위치에서 오프셋을 빼준 후 다시 route4의 길이 - 1을 더해 위치를 변경한다.

 

예를 들어 route0, 현재 위치 18에서 주사위가 2가 나온다면 새로운 위치는 18 + 5 = 20이 된다.

 

23은 route0의 길이(20) 보다 크기 때문에 route4로 변경해야 한다. 따라서 20 - 20 + 4 - 1 = 3 이 되어 route4의 마지막에 위치하여 40 점을 획득할 수 있다.

 

route1, 2, 3 에서 처리

세 루트에서는 이동 위치가 각 루트의 길이를 넘어갈 때 route4로 루트를 변경하는 작업만 수행하면 된다. 이때 각 루트의 길이를 오프셋으로 하여 이동할 위치에서 빼준다.

 

route4 에서 처리

 

이제 route0, 1, 2, 3에서 이동할 위치가 각 루트의 길이를 넘을 경우 route4로 변경 되었기 때문에 도착지로 이동하는 부분은 route4에서만 처리하면된다. 

 

말을 이동하되 이동 위치가  route4의 길이를 넘을 경우 도착지로 이동하면된다.

 

route 0 - 4에서 이동 위치가 각 루트의 길이를 넘지 않을 경우

이때는 정상적으로 각 루트 내 위치로 이동하면된다. 단 이동할 위치에 말이 존재할 경우 이동할 수 없기 때문에 각 말의 위치를 확인하고 만약 다른 말이 해당 위치에 존재 한다면 다른 말을 선택하여 처음부터 알고리즘을 수행할 수 있도록 한다.

 

Python

 

	from sys import stdin
	readline = stdin.readline
	seq = list(map(int, readline().split()))
	graph = [[i*2 for i in range(20)]]
	graph.append([13, 16, 19])
	graph.append([22, 24])
	graph.append([28, 27, 26])
	graph.append([25, 30, 35, 40])
	ans = 0
	piece = [[0, 0], [0, 0], [0, 0], [0, 0]]
	def solve(idx, point):
	global ans
	if idx == len(seq):
	ans = max(ans, point)
	return
	moves = seq[idx]
	for i in range(4):
	current, _dir = piece[i]
	_next = current + moves
	origin_dir = _dir
	# 도착 칸에 위치한 말은 넘어간다.
	if current == -1: continue
	# 0번 방향의 5, 10, 15에서 출발하는 경우 지름길로
	if (current == 5 or current == 10 or current == 15) and _dir == 0:
	_dir = current // 5
	_next = moves - 1
	# 1 - 3 루트의 크기를 넘으면 4루트로 넘어간다.
	if 0<_dir<=3 and _next >= len(graph[_dir]):
	_next -= len(graph[_dir])
	_dir = 4
	# 0 루트의 크기를 넘으면 4루트로 넘어간다.
	if _dir == 0 and _next >= len(graph[_dir]):
	temp = len(graph[_dir])
	_dir = 4
	_next = _next - temp + len(graph[_dir]) - 1
	# 도착지에 다다를 수 있는 경우는 4루트 경우 뿐
	# 4루트 크기를 넘어서면 도착지로 다다른 것으로 처리
	if _dir == 4 and _next >= len(graph[_dir]):
	piece[i] = [-1, _dir]
	solve(idx+1, point)
	piece[i] = [current, origin_dir]
	else:
	# 만약 도착지에 다른 말이 존재 한다면
	# 다음 말을 선택
	# return이 아닌 continue!!!!!!!
	flag = True
	for j in range(4):
	if _next == piece[j][0] and _dir == piece[j][1]:
	flag = False
	break
	if not flag: continue
	piece[i] = [_next, _dir]
	solve(idx+1, point + graph[_dir][_next])
	piece[i] = [current, origin_dir]
	solve(0, 0)
	print(ans)

view raw BOJ17825.py hosted with ❤ by GitHub

Java

 

	import java.io.*;
	import java.util.*;
	public class BOJ17825 {
	static int[] seq;
	static int[][] piece = {{0, 0}, {0, 0}, {0, 0}, {0, 0}};
	static int[][] graph;
	static int ans = 0;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	seq = new int[10];
	String[] line = br.readLine().split(" ");
	for(int i=0;i<10;i++){
	seq[i] = Integer.parseInt(line[i]);
	}
	graph = new int[5][];
	int[] route0 = new int[20];
	for(int i=0;i<20;i++){
	route0[i] = i * 2;
	}
	graph[0] = route0;
	int[] route1 = {13, 16, 19};
	graph[1] = route1;
	int[] route2 = {22, 24};
	graph[2] = route2;
	int[] route3 = {28, 27, 26};
	graph[3] = route3;
	int[] route4 = {25, 30, 35, 40};
	graph[4] = route4;
	solve(0, 0);
	System.out.println(ans);
	}
	public static void solve(int idx, int point){
	if(idx == seq.length){
	ans = Math.max(ans, point);
	return;
	}
	int moves = seq[idx];
	for(int i=0;i<4;i++){
	int current = piece[i][0];
	int dir = piece[i][1];
	int nc = current + moves;
	int nd = dir;
	if(current == -1) continue;
	if((current == 5 || current == 10 || current == 15) && nd == 0){
	nd = current / 5;
	nc = moves - 1;
	}
	if((nd > 0 && nd <= 3) && nc >= graph[nd].length){
	nc -= graph[nd].length;
	nd = 4;
	}
	if(nd == 0 && nc >= graph[nd].length){
	int temp = graph[nd].length;
	nd = 4;
	nc = nc - temp + graph[nd].length - 1;
	}
	if(nd == 4 && nc >= graph[nd].length){
	piece[i][0] = -1;
	piece[i][1] = nd;
	solve(idx+1, point);
	piece[i][0] = current;
	piece[i][1] = dir;
	} else {
	boolean flag = true;
	for(int j=0;j<4;j++){
	if(piece[j][0] == nc && piece[j][1] == nd){
	flag = false;
	break;
	}
	}
	if (!flag) continue;
	piece[i][0] = nc;
	piece[i][1] = nd;
	solve(idx+1, point + graph[nd][nc]);
	piece[i][0] = current;
	piece[i][1] = dir;
	}
	}
	}
	}

view raw BOJ17825.java hosted with ❤ by GitHub