[ 백준 / 17825번 ] Gold II -주사위 윷놀이 : Solved by Java

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

 

문제

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

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

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

입력

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

출력

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

 

 

[ 풀이 ] 

이 문제를 처음 보고 얼마나 막막했는지.. 후.. 이걸 도데체 어떻게 푸나 고민이 많았다.

링크드 리스트를 구현해야하나.. 근데 또 그 링크드 리스트를 어디다 저장해 두나...

그러다가 그냥 하드 코딩 형식으로 푸는 것이 맞다고 생각하였다. 

근데 그래도 안풀리는 부분이 있었는데 

코드를 보고 설명한다. 

 

[ 풀이 코드 ]  : 다들 이런 문제 어떻게들 잘 푸는지 의문이다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 주사위윷놀이 {
	static int ans;
	static int[] arr = new int[10]; 
	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++) {
			arr[i]= Integer.parseInt(st.nextToken());
		}
		int[][]map = new int[4][30];
		// 0 && 5 , 0 && 10 && 15
		map[0] =  new int[] {0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,-1,-1,-1,-1,-1,-1,-1};
		map[1] =  new int[] {0,0,0,0,0,10,13,16,19,25,30,35,40,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
		map[2] =  new int[] {0,0,0,0,0, 0, 0, 0, 0, 0,20,22,24,25,30,35,40,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
		map[3] =  new int[] {0,0,0,0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,30,28,27,26,25,30,35,40,-1,-1,-1,-1,-1};
		int[]score = new int[4];
		///40 이면 0,20으로, 25면 1,9  30이면 1,10, 35,1,11 
		
		boolean[][] v =new boolean[4][30];
		v[0][0]= true;
		check(0,new int[4], new int[4],map,v,0);//주사위 ,핀위치, map, 도착한 말 , 점수 
		System.out.println(ans);
	}

	private static void check(int N, int[] X, int[] Y, int[][] map, boolean[][] v,int score) {
		if(N==10) {
			ans = score>ans?score:ans;
			return;
		}
		for(int i =0; i< 4; i++) {
			int a = X[i];
			int b = Y[i];
			if( map[X[i]][Y[i]] ==-1) continue;
			v[X[i]][Y[i]]= false;
			int x = 0; 
			if(X[i]==0) {
				switch(Y[i]){
				case 5: x= 1; break;
				case 10: x =2; break;
				case 15: x=3; break;
				}
			}
			X[i]+=x;
			Y[i]+=arr[N];
			int m = map[X[i]][Y[i]];
			if(X[i]!=0) {
				switch(m) {
				case 40:
					X[i] = 0;Y[i]=20;
					break;
				case 25:
					X[i]=1;Y[i]=9;break;
				case 30:
					X[i] = 1;Y[i]=10;break;
				case 35 : 
					X[i]=1;Y[i]=11;break;
				}
			}
			///40 이면 0,20으로, 25면 1,9  30이면 1,10, 35,1,11 
			if(!v[X[i]][Y[i]]) {
				if(m!=-1) {
					v[X[i]][Y[i]] = true;
					check(N+1,X,Y,map,v,score+m);
					v[X[i]][Y[i]] = false;
				}else {
					//System.out.print(i+"번이 "+map[X[i]][Y[i]]+" ");
					check(N+1,X,Y,map,v,score);
				}
				
			}
			X[i]=a;
			Y[i]=b;
			v[X[i]][Y[i]]= true;
		}
	}
}

데이터 입력 받는 부분은 건너 뛰고 그 이후부터 설명한다. 

이 부분이 바로 지금 쓴 코드의 메인이라고 할 수 있다. 윷놀이 판을 상세히 싹싹 써주었다. 

30까지 한 이유는 혹시 40에도착하고 그 이후로 주사위 값이 5까지 나올 수 있으므로 더해주었다. 

그리고 현재 여기에 말이 있는지 검사할 visitied Boolean 배열 

그리고 이제 DFS를 위하여 check함수로 들어가게 되는데, 

현재 주사위 순서, 윷놀이 판의 map[]의 배열 위치 X[] , map[][]의 위치 Y( X,Y를 통해 현재 윷말의 위치를 알 수 있다. 

그리고 다른 말들과 자신의 위치를 적어둘 v, 최대값을 구하기 위한 score를 받아오게 된다. 

DFS에서 탈출하기 위한 조건은 N=10일 경우 주사위 10번을 모두 이용하였으므로 ans를 갱신해주고 return 하게 된다. 

 

그리고 이제 끔찍한 조건문이 시작되는데, 

우선 윷 말이 4개니 4번 돌도록 한다. 

르

그리고 반복이 끝나면 다시 원상복귀 시켜줘야 하므로 미리, a,b에 저장해 둔다. 

만약 map[X[i][Y[i]]가 -1인 경우 그 말은 이미 도착지점에 왔으므로 다른 말을 선택한다. 

그리고 지금 값이 파란 동그라민지 빨간 동그라민지에 따라서 x값을 수정해 준다. 

수정된 값을 X[i]에 담으면 이제, 이동해야할 말의 위치가 되고, 거기에 Y[i]에도 주사위 값만큼 더해준다. 

 

그리고 여기가 중요한 파트인데, 내가 왜 틀렸지라고 한참 생각한 부분이다. 

질문 검색을 통해 알았는데,  이 부분을 거치지 않으면, 다른 경로를 통해 같은 값으로 돌아왔을 떄의 처리가 되지 않는다.

이부분을 꼭 해두어야 한다. 만약 이 부분을 해주지 않았다면 testcase 3에서 184?값이 나온다. 

그리고 처리가 완료 되었으면, 

이제 여기에서 dfs를 돌게 되는데, 현재 위치를 방문했다고 true로 바꿔 주고, N도 더하고, score도더하고 해서 

e다음 재귀문으로 간다. 

그리고 만약 이동한 값이 m==-1이라면 도착한 경우라서 방문 체크도, score도 더해주지 않고, dfs를 돌게 된다. 

반복문의 마지막즈음으로 오면, 이제 다시 원래 값으로 원상복구 해주게 된다. 

 

이후 탈출 조건을 거쳐 

ans를 print해주면 된다.