[백준] 17825 주사위 윷놀이

 

문제

---

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

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

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

 

 

 

풀이

---

윷놀이 게임판을 Node 클래스를 선언해서 구현하였다.

static class Node{
	
	int score;
	boolean isEmpty;
	boolean isFinish;
	Node red;
	Node blue;
	
	Node(int score){
		this.score = score;
		this.blue = null;
		this.isEmpty = true;
		this.isFinish = false;
	}
	
	public Node addNext(int score) {
		Node nextNode = new Node(score);
		this.red = nextNode;
		return nextNode;
	}
	
	public static Node getBlueNode(Node start, int target) {
		Node tmp = start;
		while(true) {
			if(tmp == null) {return null;}
			if(tmp.score == target) {return tmp;}
			
			tmp = tmp.red;
		}
	}
}


static void setBoard() {
	
	start = new Node(0);
	
	Node tmp = start;
	for(int i = 2 ; i <= 40 ; i +=2 ) {
		tmp = tmp.addNext(i);
	}
	
	end = tmp.addNext(0);
	end.isFinish = true;
	end.red = end;
	
	Node crossLast = new Node(25);
	tmp = crossLast.addNext(30);
	tmp = tmp.addNext(35);
	tmp.red = Node.getBlueNode(start, 40);
	
	tmp = Node.getBlueNode(start, 10);
	tmp = tmp.blue = new Node(13);
	tmp = tmp.addNext(16);
	tmp = tmp.addNext(19);
	tmp.red = crossLast;
	
	tmp = Node.getBlueNode(start, 20);
	tmp = tmp.blue = new Node(22);
	tmp = tmp.addNext(24);
	tmp.red = crossLast;
	
	tmp = Node.getBlueNode(start, 30);
	tmp = tmp.blue = new Node(28);
	tmp = tmp.addNext(27);
	tmp = tmp.addNext(26);
	tmp.red = crossLast;
	
}

 

red  는 원래 가야하는 화살표

blue 는 지름길로 가는 화살표다.

 

 

이렇게 한 뒤 백트레킹 방식으로 말이 가는 방법을 만들어서 가게 하였다.

그 중 하나라도 겹치는 공간이 생긴다면 그 때는 0을 return 하여 점수를 세지 않는다.

 

static int game() {		
	Arrays.fill(horse, start);
	
	int score = 0;
	
	for(int i = 0 ; i < 10 ; i++) {
		Node now = horse[order[i]];
		now.isEmpty = true;
		
		for(int j =  0 ; j < move[i] ; j++) {
			if(j == 0 && now.blue != null) {
				now = now.blue;
			}
			else {
				now = now.red;
			}
		}
		
		horse[order[i]] = now;
		
		//이미 말이 있다면 불가능한 경우
		if(!now.isEmpty && !now.isFinish) {
			score = 0;
			break;
		}
		else {
			now.isEmpty = false;
			score += now.score;
		}
	}
	
	for(int i = 0 ; i < 4 ; i++) {
		horse[i].isEmpty = true;
	}
	
	return score;
}

static void permutation(int index){
	
	if(index >= 10) {
		answer = Math.max(answer, game());
		return;
	}
	
	for(int i = 0 ; i < 4 ; i++) {
		order[index] = i;
		permutation(index + 1);
	}
}

 

 

 

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	
	static int[] move;
	static int[] order;
	static Node[] horse;
	static Node start;
	static Node end;
	static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
			
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		move = new int[10];
		order = new int[10];
		horse = new Node[4];
		for(int i = 0 ; i < 10 ; i++) {
			move[i] = Integer.parseInt(st.nextToken());
		}
		
		setBoard();
		permutation(0);
		
		System.out.println(answer);
	}
	
	static int game() {		
		Arrays.fill(horse, start);
		
		int score = 0;
		
		for(int i = 0 ; i < 10 ; i++) {
			Node now = horse[order[i]];
			now.isEmpty = true;
			
			for(int j =  0 ; j < move[i] ; j++) {
				if(j == 0 && now.blue != null) {
					now = now.blue;
				}
				else {
					now = now.red;
				}
			}
			
			horse[order[i]] = now;
			
			//이미 말이 있다면 불가능한 경우
			if(!now.isEmpty && !now.isFinish) {
				score = 0;
				break;
			}
			else {
				now.isEmpty = false;
				score += now.score;
			}
		}
		
		for(int i = 0 ; i < 4 ; i++) {
			horse[i].isEmpty = true;
		}
		
		return score;
	}
	
	static void permutation(int index){
		
		if(index >= 10) {
			answer = Math.max(answer, game());
			return;
		}
		
		for(int i = 0 ; i < 4 ; i++) {
			order[index] = i;
			permutation(index + 1);
		}
	}
	
	static void setBoard() {
		
		start = new Node(0);
		
		Node tmp = start;
		for(int i = 2 ; i <= 40 ; i +=2 ) {
			tmp = tmp.addNext(i);
		}
		
		end = tmp.addNext(0);
		end.isFinish = true;
		end.red = end;
		
		Node crossLast = new Node(25);
		tmp = crossLast.addNext(30);
		tmp = tmp.addNext(35);
		tmp.red = Node.getBlueNode(start, 40);
		
		tmp = Node.getBlueNode(start, 10);
		tmp = tmp.blue = new Node(13);
		tmp = tmp.addNext(16);
		tmp = tmp.addNext(19);
		tmp.red = crossLast;
		
		tmp = Node.getBlueNode(start, 20);
		tmp = tmp.blue = new Node(22);
		tmp = tmp.addNext(24);
		tmp.red = crossLast;
		
		tmp = Node.getBlueNode(start, 30);
		tmp = tmp.blue = new Node(28);
		tmp = tmp.addNext(27);
		tmp = tmp.addNext(26);
		tmp.red = crossLast;
		
	}
	
	static class Node{
		
		int score;
		boolean isEmpty;
		boolean isFinish;
		Node red;
		Node blue;
		
		Node(int score){
			this.score = score;
			this.blue = null;
			this.isEmpty = true;
			this.isFinish = false;
		}
		
		public Node addNext(int score) {
			Node nextNode = new Node(score);
			this.red = nextNode;
			return nextNode;
		}
		
		public static Node getBlueNode(Node start, int target) {
			Node tmp = start;
			while(true) {
				if(tmp == null) {return null;}
				if(tmp.score == target) {return tmp;}
				
				tmp = tmp.red;
			}
		}
	}	
}