백준 17825 : 주사위 윷놀이

https://www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

[ 문제풀이 ]

단순 구현 문제이다. 총 경우의 수가 4^10 = 약 100만 정도이기 때문에 모든 경우의 수를 다 시뮬레이션 해보면 된다.

조심해야 할 점은 같은 번호의 칸이 존재하기 때문에 놓을 수 있는 경우도 생긴다.

이를 관리하기 위해 각 말에다 방향을 부여하여 관리한다. 16, 22, 24, 26, 28은 방향이 다르다면 같은 번호라도 놓을 수 있다. 30은 앞의 칸보다 조금 생각해야 할 게 많다.

이를 쉽게 하기 위해서 중간의 30을 겹치지 않는 다른 수로 변경하면 방향에 상관없이 관리할 수 있다. 사실 위 방법처럼 모든 번호를 안 겹치도록 변경한다면 훨씬 구현하기 쉬울 것이다.

​나의 방법은 매번 새로운 Game을 생성하기 때문에 메모리를 상당히 많이 잡아먹는 좋지 못한 코드이다. 다음에 다시 풀게 되면 그때는 매번 Game을 생성하지 말고 모든 번호를 안 겹치도록 변경하여 전역 변수로 map을 선언하여 관리하도록 해야겠다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	
	static int[][] map = {{10, 13, 16, 19, 25, 39, 35, 40, 42, 42, 42, 42, 42},
						  {20, 22, 24, 25, 39, 35, 40, 42, 42, 42, 42, 42, 42},
						  {30, 28, 27, 26, 25, 39, 35, 40, 42, 42, 42, 42, 42}};
	static String[] cmd;
	static Queue<Game> q;
	
	static class Node {
		int pos, direct;
		
		public Node(int pos, int direct) {
			this.pos = pos;
			this.direct = direct;
		}
	}
	
	static class Game {
		int score, turn;
		Node[] node;

		public Game(int turn, int score) {
			node = new Node[4];
			this.turn = turn;
			this.score = score;
		}
		
		public void selectNode() {
			for (int i = 0; i < 4; ++i) {
				if (node[i] == null) continue;
				//새 게임을 생성
				Game g = makeNewGame();
				//i번째 말을 움직일 수 있다면
				if (g.isVaild(i)) {
					q.offer(g);
				}
			}
		}
		
		public Game makeNewGame() {
			Game g = new Game(turn + 1, score);
			for (int i = 0; i < 4; ++i) {
				if (node[i] == null) g.node[i] = null;
				else g.node[i] = new Node(node[i].pos, node[i].direct);
			}
			return g;
		}
		
		public boolean isVaild(int idx) {
			int next_Pos = node[idx].pos;
			int direct = node[idx].direct;
			int move = Integer.parseInt(cmd[turn]);
			
			//방향이 3인 경우 +2칸
			if (direct == 3) next_Pos += 2 * move;
			//다른 경우는 미리 만들어 놓은 맵의 위치로 움직임
			else {
				int now_Pos = get_Position(next_Pos, direct);
				next_Pos = map[direct][now_Pos + move];
			}
			
			//도착 범위를 벗어나면
			if (next_Pos > 40) {
				node[idx] = null;
				return true;
			}
			
			//말을 놓을 수 있는지 판단
			for (int i = 0; i < 4; ++i) {
				if (i == idx || node[i] == null) continue;
				if (next_Pos == node[i].pos) {
					if (next_Pos == 16 || next_Pos == 22 || next_Pos == 24 || next_Pos == 26 || next_Pos == 28) {
						if (direct == node[i].direct) {
							return false;
						}
					} else {
						return false;
					}
				}
			}
			
			if (next_Pos == 39) score += 30;
			else score += next_Pos;
			node[idx].pos = next_Pos;
			
			//파란 칸인 경우 방향을 3에서 바꿔줘야함 
			if (next_Pos == 10) node[idx].direct = 0;
			else if (next_Pos == 20) node[idx].direct = 1;
			else if (next_Pos == 30) node[idx].direct = 2;
			
			return true;
		}
		
		//현재 방향에서 어디에 위치하고 있는지 찾음
		public int get_Position(int now_Pos, int direct) {
			for (int i = 0; i < 10; ++i) {
				if (map[direct][i] == now_Pos) {
					return i;
				}
			}
			return -1;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		cmd = br.readLine().split(" ");
		q = new LinkedList<>();
		int answer = 0;
		
		Game g = new Game(-1, 0);
		for (int i = 0; i < 4; ++i) g.node[i] = new Node(0, 3);
		
		q.offer(g);
		while (!q.isEmpty()) {
			g = q.poll();
			answer = Math.max(answer, g.score);
			if (g.turn < 9) g.selectNode();
		}

		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}
}