[BOJ 17825] 주사위 윷놀이 (Java)

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

17825번: 주사위 윷놀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static class Pos{
		int r,c,d;
		Pos(int r, int c, int d){
			this.r=r;
			this.c=c;
			this.d=d;
		}
	}
	static int[] dr= {1,0,-1};
	static int[] dc= {0,1,0};
	static int[] dices=new int[10];
	static int[] scores=new int[4]; 
	static boolean[] isArrived=new boolean[4];
	static Pos[] pos=new Pos[4];
	static int[][] map=new int[22][5];
	static int max=Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		for (int i=0; i<10; i++) {
			dices[i]=Integer.parseInt(st.nextToken());
		}
		init();
		dfs(0, new int[10]);
		System.out.println(max);
	}
	
	public static void init() {
		int num=0;
		for (int i=0; i<22; i++) {
			map[i][0]=num;
			if (i==5) {
				int temp=num+3;
				for (int j=1; j<=3; j++) {
					map[i][j]=temp;
					temp+=3;
				}
				temp=25;
				for (int j=i; j>0; j--) {
					map[j][4]=temp;
					temp+=5;
				}
			}
			if (i==10) {
				int temp=num+2;
				for (int j=1; j<=2; j++) {
					map[i][j]=temp;
					temp+=2;
				}
				temp=25;
				for (int j=i; j>=i-4; j--) {
					map[j][3]=temp;
					temp+=5;
				}
			}
			if (i==15) {
				int temp=num-2;
				for (int j=1; j<=3; j++) {
					map[i][j]=temp;
					temp-=1;
				}
				temp=25;
				for (int j=i; j>=i-4; j--) {
					map[j][4]=temp;
					temp+=5;
				}
			}
			num+=2;
		}
		for (int i=0; i<4; i++) {
			pos[i]=new Pos(0,0,0);
		}
	}
	
	
	public static void dfs(int turn, int[] pick) {
		boolean isEnd=true;
		for (int i=0; i<4; i++) {
			if (!isArrived[i]) isEnd=false; 
		}
		if (isEnd || turn==10) {
			int sum=0;
			for (int i=0; i<4; i++) {
				sum+=scores[i];
			}
			if (sum>max) {
				max=sum;
			}
			return;
		}
		for (int i=0; i<4; i++) {
			if (isArrived[i]) continue;
			int prev_r=pos[i].r;
			int prev_c=pos[i].c;
			int prev_d=pos[i].d;
			int moveSum=move(i, dices[turn]);
			if (moveSum==-1) continue; 
			pick[turn]=i;
			dfs(turn+1, pick);
			scores[i]-=moveSum;
			isArrived[i]=false;
			pos[i].r=prev_r;
			pos[i].c=prev_c;
			pos[i].d=prev_d;
		}
	}

	private static int move(int num, int moves) {	
		int sum=0;
		int nr=pos[num].r, nc=pos[num].c;
		int d=pos[num].d;
		for (int i=0; i<moves; i++) {
			nr+=dr[pos[num].d];
			nc+=dc[pos[num].d];
			if (map[nr][nc]==42) {
				isArrived[num]=true;
				break;
			}
			if (map[nr][nc]==25) {
				nr=5; nc=4;
				pos[num].d=2;
			}
			if (map[nr][nc]==40) {
				nr=20; nc=0;
				pos[num].d=0;
			}
		}
		if (!isArrived[num]) {
			sum=map[nr][nc];
			for (int i=0; i<4; i++) {	
				if (pos[i].r==nr && pos[i].c==nc) {
					pos[num].d=d;	
					return -1;
				}
			}
		}
		if (map[nr][nc]==10 || map[nr][nc]==20 || (nr==15 && nc==0)) {
			pos[num].d=1;		
		}
		if (map[nr][nc]==25) {
			pos[num].d=2;
		}
		pos[num].r=nr;
		pos[num].c=nc;
		scores[num]+=sum;
		return sum;
	}
	


}

복잡하게 풀었다.. map을 어떻게 표현해야 될지 고민을 많이 했고, 2차원 배열에 map 을 표시하는 걸로 했다.

그러나 이렇게 했더니 좌표 조정 과정에서 분명 같은 칸에 있는데 좌표가 서로 달라 같은 칸에 있지 않다고 표시가 되어서 중간에 25나 40이 나오면 좌표를 조정해야 하는..이런 번거로움이 있다.

 

1. DFS 로 중복 순열을 구해준다. (1번~4번 말)

2. DFS로 말을 뽑아줄 때마다 move 함수를 이용해 해당 말을 움직여줘서, map 내에서의 말의 위치를 나타내는 pos 와 score을 업데이트 시켜준다. (해당 부분 탐색이 종료 시에는 pos, score을 원래로 되돌려줌)

3. 움직여주는 함수는 move 로, 말의 위치를 나타내는 pos 배열을 쭉 돌아 도착 칸에 다른 말이 있는지 체크한다.

 

다른 분들의 코드를 보니,(https://haejun0317.tistory.com/163 님)

map 배열에 다음에 이동할 노드의 번호를 붙여서 하면 간단해짐을 알 수 있었다.

turn 배열에 방향 전환이 되는 노드를 따로 관리해서 한다.

현재 말의 위치를 저장하고, 그 위치가 방향 전환해야 되는 노드면 바꿔주고=> move 수만큼 map 배열을 돌려준다면 도착 지점이 나오게 된다. 또한 점수의 총합을 구하는 것이므로 파라미터로 구하면 더 간결해진다.