[BOJ-17825]주사위 윷놀이 -Java

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

17825번: 주사위 윷놀이

package 시뮬레이션;

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

public class boj_17825_주사위윷놀이 {
	static int result, info[], map[][], permuArr[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		result = Integer.MIN_VALUE;
		info = new int[10];
		permuArr = new int[10];
		map = new int[6][];

		map[0] = new int[] { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38 };
		map[1] = new int[] { 13, 16, 19 };
		map[2] = new int[] { 22, 24 };
		map[3] = new int[] { 28, 27, 26};
		map[4] = new int[] { 25,30,35};
		map[5] = new int[] { 40 };

		for (int i = 0; i < 10; i++) { // 주사위 굴리는 정보
			info[i] = Integer.parseInt(st.nextToken());
		}
		for (int i = 1; i <= 4; i++) { // 말 개수 선택
			dfs(i, 0); // 중복 순열
		}
		System.out.println(result);

	}

	private static void dfs(int arange, int cnt) {
		if (cnt == 10) {
			moveHorse(); // 말 이동
			return;
		}

		for (int i = 0; i < arange; i++) {
			permuArr[cnt] = i;
			dfs(arange, cnt + 1);
		}
	}

	private static void moveHorse() {
		int horseIndex[] = { -1, -1, -1, -1 }; // 각 말의 초기 좌표는 -1
		int horseLines[] = { 0, 0, 0, 0 };
		int totalScore = 0;

		for (int d = 0; d < 10; d++) {
			int score = 0; // 이번 주사위 굴린거 점수
			int horseNo = permuArr[d]; // 현재 말 번호는 ?
			int horseLine=horseLines[horseNo]; //현재 말이 몇 번 라인에 있는지 (0,1,2,3)
			int horseIdx=horseIndex[horseNo]; //현재 말의 인덱스
			int dice = info[d]; // 몇칸만큼 가는지
			
			if(horseLine==6) continue; //이미 통과 했다면 그냥 넘어감
			
			if(horseLine==0 && horseIdx!=-1) { //0번 라인일 떄 
				if(map[0][horseIdx]==10) { //10에 있다면 파란 화살표 따라가야 한다
					horseLine=1;
					horseIdx=-1;
				}
				else if(map[0][horseIdx]==20) { //20에 있다면 파란 화살표 따라가야 한다
					horseLine=2;
					horseIdx=-1;
				}
				else if(map[0][horseIdx]==30) { //30에 있다면 파란 화살표 따라가야 한다
					horseLine=3;
					horseIdx=-1;
				}
			}
			
			
			for(int i=1; i<=dice; i++) {
				if(horseLine==6) break;
				if(++horseIdx==map[horseLine].length) { //현재 라인의 끝가지 왔다면
					if(horseLine==0) {
						horseLine=5;
						horseIdx=0;
						continue;
					}
					else if(horseLine==1 || horseLine==2 || horseLine==3) {
						horseLine=4;
						horseIdx=0;
						continue;
					}
					else if(horseLine==4)  {
						horseLine=5;
						horseIdx=0;
						continue;
					}
					else if(horseLine==5) {
						horseLine=6;
						horseIdx=0;
						continue;
					}
				}
			}
			
			if( horseLine==6) {
				horseLines[horseNo]=horseLine;
				continue; //이미 통과 했다면 그냥 넘어감
			}
			
			if(!isDuplicate(horseIndex,horseLines, horseIdx, horseLine)) { //안겹치면 점수더해주고 값 옮겨줌
				horseIndex[horseNo]=horseIdx;
				horseLines[horseNo]=horseLine;
				totalScore+=map[horseLine][horseIdx];
			}
			else return;

		}

		result = Math.max(result, totalScore); // 마지막에 스코어랑 result확인

	}

	private static boolean isDuplicate(int[] horseIndex, int[] horseLines, int horseIdx, int horseLine) {
		for(int i=0; i<4; i++) {
			if(horseIndex[i]==horseIdx && horseLines[i]==horseLine) return true;
		}
		return false;
	}

}

소요시간 : 1시간 45분

 

이 문제도 어려웠습니다....2일인가 3일전에 한번 풀었는데 잘못접근해서 틀렸었는데

오늘 다시 풀어보니 풀렸습니다~

 

우선 문제를 풀기전에 윷판을 어떻게 구성할지에 대해 많이 고민했습니다.

 

윷판의 구성은 

        map[0] = new int[] { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38 };
		map[1] = new int[] { 13, 16, 19 };
		map[2] = new int[] { 22, 24 };
		map[3] = new int[] { 28, 27, 26};
		map[4] = new int[] { 25,30,35};
		map[5] = new int[] { 40 };

이런 식으로 만들었습니다.

map[0] 은 10 ,20 ,30을 그냥 지나쳣을 때 즉 빨간화살표만 따라갔을 때 가는 경로입니다.

map[1] 은 10에서 출발할때 가는 경로입니다.

map[2] 는 20에서 출발할때 가는 경로입니다.

map[3] 은 30에서 출발할때 가는 경로입니다.

이때 10, 20, 30을 밟고 가게 되면 25,30,35,40은 공유하는 지역이 됩니다.

map[4] 는 map[1],map[2],map[3]이 끝나고 공유하게 되는 지역입니다.

map[5] 는 도착지전의 바로 앞인 40이고, 어떠한 경로로 오든 공유하는 지역입니다.

 

그리고 각 말의 현재 위치는 

horseLines(몇번맵인지) 와 horseIndex(맵안에서 인덱스)를 통해 유지 하였습니다.

 

윷판은 이런식으로 구성하였습니다. 로직을 살펴보게 되면

 

1. 중복순열을 구한다. (중복순열을 통해서 10번의 주사위가 어떤 순서로 몇번말에게 할당될지 정해줍니다.)

2. 말을 이동시킨다

  - 이때 map[i]의 길이를 구해서 인덱스가 map[i].length와 같아지게 되면 다음 맵으로 이동시켜주었습니다.

    map[0]의 마지막 인덱스보다 인덱스가 커지게 되면 map[5]로 보내주고,

    map[1],map[2],map[3]의 마지막 인덱스보다 인덱스가 커지게 되면 map[4]로 보내주고

    map[4]의 마지막 인덱스보다 인덱스가 커지게 되면 map[5]로 보내주었습니다.

  - 말이 도착지점에 도착했다는 표시로 horseLines를 6으로 표시해주었습니다.

3. 말이 겹치는지를 해준다.

4. 말이 안겹친다면 점수계산

 

 

끝~~