[백준] 17825.주사위 윷놀이 (java) / 시뮬레이션

@시뮬레이션 / 1h 13m (필기 13m, 디버깅 34m)

2019년 하반기 삼성전자(ce/im부문) 코딩테스트 2번 문제였다.

익숙한 문제 스타일이 아니고 + 도대체 이건 뭐지 싶은 그림 덕에 멘붕오기 딱 좋은 문제다.

실제로 시험장에서 멘붕와서 못 풀었던 문제.

12월에 배워서 풀었고, 이번에 다시 한 번 풀었다.

 

방법을 알면 쉽게 풀 수 있는 문제지만, 그 방법을 떠올리기가 생각보다 까다로운 것 같다.

 

문제 링크

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

17825번: 주사위 윷놀이

 

구현 포인트

흔한 문제 형식이 아니라 멘붕오기 쉬운 문제인데,

파란점일 때 / 아닐 때를 구분해서 리스트를 구현해주면 생각보다 쉽게 풀 수 있다.

 

class Node {

   int score; //해당 칸의 점수

   int red;    //빨간 화살표로 이동할 경우의 다음 점

   int blue;   //파란 화살표로 이동할 경우의 다음 점

   boolean isBlue;  //파란 점인지 여부

}

 

이렇게 클래스를 하나 생성하고,

Node[] 배열을 만들어서, 각 번호에 Node를 생성해서 넣어준다.

 

문제에서는 칸의 번호와 점수가 동일한데, 같은 번호가 있는 칸이 두개씩 있는 경우가 있어서,

겹치는 번호들에 한해서 번호를 바꿔서 지정했다.

체크 표시를 한 점이 번호를 바꾼 점이다.

 

+ 도착점을 처리하기 위해서, 도착 점인 42번 점은 다음 점도 42가 되게 해서, 범위를 초과하지 않게끔 설정했다.

 

삽질 포인트

1. 나름 편하게 하려고 Node에 생성자를 두개 지정해 줬다.

아래 생성자는 파란 점일 경우 이동 방향을 지정해주는 생성자

인자의 개수는 똑같지만, 매개변수 자료형이 달라서 overloading 되니까 상관없지! 라고 생각했다.

 

 

문제는, 이렇게 짝수번째 숫자들에 대해서는 첫번째 생성자를 이용해 이미 점수와 빨간 화살표 지정 방향을 다 넣어놓은 상태였는데

그 밑에서 두번째 생성자를 불러버리면, new Node로 새롭게 생성해버려서, 기존에 저장해놨던 내용이 사라지고

score와 red가 모두 0으로 바뀌게 된다.

전혀 생각하지 못했던 부분이라 이 부분을 찾느라 고생했다 ㅠㅠ

생성자를 쓰면 매번 새롭게 생성되므로, 다른 값을 추가하고 싶을 때에는 .으로 접근해서 설정할 것!

 

 

2.내가 지정한 점들과, 문제에서 주어진 점 간에 헷갈려서 점수를 잘못 지정해줘서.. 이거 찾느라 시간 좀 썼다ㅠ

 

 

코드

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

public class Main {
	
	private static class Node {
		int score, blue, red;
		boolean isBlue = false;
		
		Node (int score, int red) {
			this.score = score;
			this.red = red;
		}
//		Node (int blue, boolean isBlue) {
//			this.blue = blue;
//			this.isBlue = isBlue;
//		}
	}
	
	private static int max = 0, permu[], step[], now[];
	private static boolean[] existCheck;
	private static Node[] map;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		map = new Node[43];
		permu = new int[10];
		
		step = new int[10];
		for (int i = 0; i < 10; i++)
			step[i] = Integer.parseInt(st.nextToken());
		
		for (int i = 0; i <= 40; i += 2)
			map[i] = new Node(i, i + 2);
		
		map[10].isBlue = map[20].isBlue = map[30].isBlue = true;
		map[10].blue = 11;
		map[20].blue = 17;
		map[30].blue = 31;
		
//		map[10] = new Node(11 , true);
//		map[20] = new Node(17 , true);
//		map[30] = new Node(31 , true);
		
		map[11] = new Node(13 , 13);
		map[13] = new Node(16 , 15);
		map[15] = new Node(19 , 25);
		map[17] = new Node(22 , 19);
		map[19] = new Node(24 , 25);
		map[25] = new Node(25 , 37);
		map[31] = new Node(28 , 33);
		map[33] = new Node(27 , 35);
		map[35] = new Node(26 , 25);
		map[37] = new Node(30 , 39);
		map[39] = new Node(35 , 40);
		map[42] = new Node(0, 42);
		
		permu[0] = 0;
		permu(9, 0);
		System.out.println(max);
	}

	private static void permu(int n, int k) {
		if (n == k) {
			now = new int[4];
			existCheck = new boolean[43];
			move();
			return;
		}
		
		for (int i = 0; i < 4; i++) {
			permu[k] = i;
			permu(n, k + 1);
			permu[k] = -1;	//굳이 안해줘도 되긴 함 
		}
	}

	private static void move() {
		int score = 0;
		
		for (int i = 0; i < 10; i++) {
			int end = horseMove(permu[i], step[i]);
			if (end == -1) return;
			now[permu[i]] = end;
			score += map[end].score;
		}
		if (max < score) max = score;
	}

	private static int horseMove(int horse, int step) {
		int temp = now[horse];
		
		for (int i = 0; i < step; i++) {
			if (i == 0 && map[temp].isBlue) {
				temp = map[temp].blue;
				continue;
			}
			temp = map[temp].red;
//			if (temp == 42) break;
//			위에서 42번 점의 다음 점도 42번 점으로 돌게 처리해줘서 이 코드는 필요 없다!
		}
		
		if (temp <= 40 && existCheck[temp]) {
			return -1;
		} else {
			existCheck[now[horse]] = false;
			existCheck[temp] = true;
			return temp;
		}
	}
}

아래가 두달 전에 배워서 푼 코드(거의 따라 친 수준..), 위가 이번에 혼자 푼 코드

 

배워서 풀었을 때 보다 조금 더 간단하게 푼 것 같다.

그래도 혼자 풀어내서 뿌듯하다.

 

끝!