[BaekJoon] 백준 17825번 _ 주사위 윷놀이 for JAVA

 

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

17825번: 주사위 윷놀이

 

 

문제

 

 

---

 

백트래킹으로 풀었다.

 

 

생각보다 어려운 문제이다. 진짜로....

 

 

윷놀이 판을 어떻게 설계할지가 제일 고민되는 문제였고 생각 없이 풀었더니 3번 테케에서 틀렸다~!

 

 

일반 계속 틀린 이유

1. hashMap 사용하고 value를 배열로 넣어놓았는데 get으로 value값을 받아오니 그 배열을 사용하면 map에 있는 value값도 바뀌었다. 배열이라서 그런가봄 것참;;

2. 이것때문에 코드 고쳤는데 이유를 생각 안하고 고쳤더니 같은 오류가 다시 발생함. 근데 이유를 몰랐기 때문에 저 이유일거라고 짐작을 못함 그래서 일일히 디버깅하다가 한참 뒤에 발견

3. 갈 수 있는 윷놀이 판의 루트를 4가지로 나눠서 2차원 배열로 구현했음. 근데 이렇게 했더니 마지막에 40에서 겹칠 때를 고려하는걸 잊어버림 그래서 테케3에서 214 아니고 218만 계속 나옴.. 얘도 30분 이상 고민한듯...

 

 

느낀점 : 엥? 하고 넘어가지 말고 이유를 분석하자.

 

 

풀이과정

0. 윷놀이 판을 어떻게 짜지?

    - 갈 수 있는 윷놀이 판 루트를 4가지로 나눔. 빨간색 화살표일 때, idx 5에서 파란색으로 갈 때, 10에서 파랑, 15에서 파랑 이렇게 루트       를 나눴다.

    - 그래서 x가 0일 때 : 빨간 루트, 1일 때 : idx=5라서 파란색 루트 탈 때, ... 이렇게 4가지 루트로 구현

    - 고려할점 : 파란색 루트를 탔을 때 밑에 그림에서 파란색으로 칠한 부분은 겹칠 수 있는 부분임 

    - 그리고 빨간색 루트를 탔을 때 파란색 루트와 겹칠 수 있는 부분은 '40'일 때! 이다. (도착 직전 40부분) 이거 고려 해줘야 테케3에서       안틀림

1. 백트래킹으로 재귀 돌리기 위해 필요한 파라미터 : 현재 cnt (10에서 멈춤), 현재 total값

2. 재귀탈 수 있는 곳 : 내가 가려는 곳에 아무것도 없음

 

 

코드

import java.util.*;
import java.io.*;

public class Main {
	static int[][] map = {{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40},
						{10,13,16,19,25,30,35,40},
						{0,20,22,24,25,30,35,40},
						{30,28,27,26,25,30,35,40}};
	static HashMap<Integer, int[]> horse = new HashMap<>(); // 말 map번호, index (i,j)
	static int[] score = new int[10];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		horse.put(0, new int[] {0,0});
		horse.put(1, new int[] {0,0});
		horse.put(2, new int[] {0,0});
		horse.put(3, new int[] {0,0});
		
		for(int i=0; i<10; i++) {
			score[i] = Integer.parseInt(st.nextToken());
		}
		backtracking(0,0);
		
		System.out.println(answer);
		
	}
	static int answer = Integer.MIN_VALUE;
	private static void backtracking(int cnt, int total) {
		if(cnt==10) {
			answer = Math.max(answer, total);
			return;
		}
		
		for(int i=0; i<4; i++) { // i가 말 번호 
			if(!horse.containsKey(i)) continue;
			// choose horse
			int previous[] = horse.get(i);
			int p1 = previous[0];
			int p2 = previous[1];
			int h[] = horse.get(i); // 움직이려는 말의 맵 번호, 현재 idx 
			int nextRoot = h[0];
			int nextIdx = h[1];
			nextIdx = nextIdx + score[cnt];
			if(nextRoot == 0 && nextIdx == 5) {
				nextRoot = 1;
				nextIdx = 0;
			} else if(nextRoot == 0 && nextIdx == 10) {
				nextRoot = 2;
				nextIdx = 1;
			} else if(nextRoot == 0 && nextIdx == 15) {
				nextRoot = 3;
				nextIdx = 0;
			}
            
            // 무조건 갈 수 있는 경우: '도착'에 도착해서 이동을 마치는 경우 
			if(nextIdx >= map[nextRoot].length) {
				horse.remove(i);
				backtracking(cnt+1, total);
				horse.put(i, new int[] {p1,p2});
				continue;
			}
			
			// 갈 수 없는 경우 : 내가 가려는 곳에 말이 있음
			if(confirm(i, new int[] {nextRoot,nextIdx})) { // 놓을 수 있다면 
				horse.put(i, new int[] {nextRoot,nextIdx});
				backtracking(cnt+1, total+map[nextRoot][nextIdx]);
				horse.put(i, new int[] {p1,p2});
			}
		}
	}
	private static boolean confirm(int horseCnt, int[] h) { // 현재 놓으려는 말 번호, []
		int horseRoot = h[0];
		int horseIdx = h[1];
		
		// 다른 말과 위치가 같은지 확인 
		// 빨간색 루트일 경우 다른 맵과 겹치는지 확인 ㄴㄴ 
		// 파란색 루트일 경우 map1,2,3과 서로 겹치는지 확인해야함 
		for(int i=0; i<4; i++) {
			if(i == horseCnt || !horse.containsKey(i)) continue;
			int other[] = horse.get(i);
			int root = other[0];
			int idx = other[1];
			
			// 같은 루트임 
			if(horseRoot == root) {
				if(horseIdx == idx) return false;
			}
			// 둘 다 파란색 루트 
			else if(horseRoot != 0 && root != 0) {
				// 인덱스 4 이상일 때 겹치는지 확인 
				if(horseIdx >= 4 && idx >= 4) {
					if(horseIdx == idx) return false;
				}
			}
			// 40일 때는 인덱스가 달라서 따로 빼줭 
			else if(map[horseRoot][horseIdx] == 40 && map[root][idx]==40) return false;
		}
		return true;
	}

}

 

 

 

성능

 

 

 

주사위로 나오는 수가 무조건 10개로 고정이어서 말 1~4를 순열 돌리고 그대로 움직여줘도 된다.

 

어차피 완탐인건 똑같음요