[JAVA] 백준 주사위 윷놀이

Node.next(연결된 객체1)

addNext를 통해

Node.fastPath(연결되 객체2)

permutation

order[i]번째에 해당하는 Node[] horse에 넣어

Max값과 방문한 노드값들의 합(gamestart메소드 return값)을 비교

단순 구현문제인줄 알았는데, 연결리스트를 통한 구현이어서 어려웠다.

 

노드는 아래 그림과 같이 순서대로 연결한다.

https://zoosso.tistory.com/232

1. 직선방향으로 시작~도착까지 Node.next(연결된 객체1)로 연결

 

2. 지름길 같은경우는 addNext를 통해 10,20,30에 해당하는 노드를 찾아서 Node.fastPath(연결되 객체2)에 연결해준다.

 

3. permutation을 통해서 order[] 배열에 순열 경우의수를 dfs로 탐색한다.

 

4. dfs로 깊이 10까지 채웠으면, 해당 order[]배열을 통해 order[i]번째에 해당하는 Node[] horse에 넣어주는 gamestart를 시행한다.

 

5. 한가지 order경우의 수에 대해 gamestart를 완료했으면, Max값과 방문한 노드값들의 합(gamestart메소드 return값)을 비교해준다.

 

6. permutation이므로 order dfs(depth=11)일때 모든경우에 대하여 방문노드 합을 비교하여 최대값을 알아낸다.

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

public class Main {

​​​​private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
​​​​private static int[] dice, order; // 주사위, 배치순서
​​​​private static Node[] horse; // 4개의 말
​​​​private static Node start; // 시작지점
​​​​private static int answer = Integer.MIN_VALUE;

​​​​static class Node {   // 윷놀이 판을 연결 리스트 구조에 담는다.
​​​​​​​​int score;        // 윷놀이판에서 해당 칸의 점수.
​​​​​​​​boolean isEmpty;  // 해당 칸이 비었는지. (다른 말이 와있는 칸인지 체크)
​​​​​​​​boolean isFinish; // 도착 지점인지를 체크.
​​​​​​​​Node next;
​​​​​​​​Node fastPath;    // 윷놀이판에서 10, 20, 30은 두 가지 방향이 존재한다.

​​​​​​​​public Node(int score) {
​​​​​​​​​​​​this.score = score;
​​​​​​​​​​​​this.isEmpty = true;
​​​​​​​​}

​​​​​​​​// 노드 연결 (연결 리스트 구조)
​​​​​​​​public Node addNext(int score) {
​​​​​​​​​​​​Node nextNode = new Node(score);
​​​​​​​​​​​​this.next = nextNode;
​​​​​​​​​​​​return nextNode;
​​​​​​​​}

​​​​​​​​// 노드 찾기 (지름길 놓는 지점을 찾기 위한 함수)
​​​​​​​​public static Node getNode(Node start, int target) {
​​​​​​​​​​​​Node temp = start;
​​​​​​​​​​​​while (true) { // 시작 지점부터 탐색해가며 특정 노드를 찾습니다.
​​​​​​​​​​​​​​​​if (temp == null) return null;
​​​​​​​​​​​​​​​​if (temp.score == target) return temp;
​​​​​​​​​​​​​​​​temp = temp.next;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

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

​​​​​​​​dice = new int[10 + 1];
​​​​​​​​order = new int[10 + 1];
​​​​​​​​horse = new Node[4 + 1];
​​​​​​​​for (int i = 1; i <= 10; i++) {
​​​​​​​​​​​​dice[i] = Integer.parseInt(st.nextToken());
​​​​​​​​}

​​​​​​​​init(); // 윷놀이판 설정
​​​​​​​​permutation(1); // 10개의 주사위 결과를 말들에게 할당
​​​​​​​​System.out.println(answer);
​​​​}

​​​​private static void permutation(int depth) {//order에 순열순서 재귀로 넣음
​​​​​​​​if (depth >= 11) {
​​​​​​​​​​​​answer = Math.max(answer, gameStart());
​​​​​​​​​​​​return;
​​​​​​​​}

​​​​​​​​for (int i = 1; i <= 4; i++) {
​​​​​​​​​​​​order[depth] = i;
​​​​​​​​​​​​permutation(depth + 1);
​​​​​​​​}
​​​​}

​​​​private static int gameStart() {
​​​​​​​​Arrays.fill(horse, start); // 말들을 시작 지점으로 배치

​​​​​​​​int score = 0;
​​​​​​​​for (int i = 1; i <= 10; i++) {
​​​​​​​​​​​​Node cur = horse[order[i]]; // !!!순열로 할당된 순서대로 말들을 움직입니다.!!!
​​​​​​​​​​​​cur.isEmpty = true; // 현재 있는 칸을 비워줍니다.

​​​​​​​​​​​​for (int j = 1; j <= dice[i]; j++) { // 주사위에 나온 수치만큼 이동합니다.
​​​​​​​​​​​​​​​​if (j == 1 && cur.fastPath != null) { // 처음 이동을 시작하려는 위치가 파란색 칸이라면.
​​​​​​​​​​​​​​​​​​​​cur = cur.fastPath; // 지름길로 이동(파란색 방향)
​​​​​​​​​​​​​​​​} else {
​​​​​​​​​​​​​​​​​​​​cur = cur.next; // 빨간색 방향으로 이동
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}

​​​​​​​​​​​​horse[order[i]] = cur; // 이동 후, 말 위치 설정

​​​​​​​​​​​​if (!cur.isEmpty && !cur.isFinish) { // 이동을 마친 칸에 다른 말이 있다면, 해당 말은 고를 수 없다.
​​​​​​​​​​​​​​​​score = 0; // 주사위에 할당받은 말들의 순서가 무효처리.
​​​​​​​​​​​​​​​​break;
​​​​​​​​​​​​} else {
​​​​​​​​​​​​​​​​cur.isEmpty = false; // 말이 존재하는 것으로 표시
​​​​​​​​​​​​​​​​score += cur.score; // 해당 칸의 점수 추가
​​​​​​​​​​​​}
​​​​​​​​} // 게임종료

​​​​​​​​// 다음 게임을 위해 말들의 위치를 지워줍니다.
​​​​​​​​for (int i = 1; i <= 4; i++)
​​​​​​​​​​​​horse[i].isEmpty = true;

​​​​​​​​return score; // 획든한 점수 반환
​​​​}

​​​​private static void init() {
​​​​​​​​start = new Node(0); // 시작 지점. (시작 지점의 스코어는 0)

​​​​​​​​Node temp = start;
​​​​​​​​for (int i = 2; i <= 40; i += 2) {
​​​​​​​​​​​​temp = temp.addNext(i); // 윷놀이판 바깥쪽 경로 설정
​​​​​​​​}

​​​​​​​​Node end = temp.addNext(0); // 도착 지점. (도착 지점의 스코어는 0)
​​​​​​​​end.isFinish = true;
​​​​​​​​end.next = end; // 자기자신을 가르키도록 설정 (도착 지점을 넘어서는 이동에 대해 NPE 방지)

​​​​​​​​Node crossroads = new Node(25); // 가운데 교차점 (score = 25)

​​​​​​​​// 교차점(25) -> 30 -> 35 -> 40
​​​​​​​​temp = crossroads.addNext(30);
​​​​​​​​temp = temp.addNext(35);
​​​​​​​​temp.next = Node.getNode(start, 40);

​​​​​​​​// 10 -> 13 -> 16 -> 19 -> 25(교차점)
​​​​​​​​temp = Node.getNode(start, 10);
​​​​​​​​temp = temp.fastPath = new Node(13);
​​​​​​​​temp = temp.addNext(16);
​​​​​​​​temp = temp.addNext(19);
​​​​​​​​temp.next = crossroads;

​​​​​​​​// 20 -> 22 -> 24 -> 25(교차점)
​​​​​​​​temp = Node.getNode(start, 20);
​​​​​​​​temp = temp.fastPath = new Node(22);
​​​​​​​​temp = temp.addNext(24);
​​​​​​​​temp.next = crossroads;

​​​​​​​​// 30 -> 28 -> 27 -> 26 -> 25(교차점)
​​​​​​​​temp = Node.getNode(start, 30);
​​​​​​​​temp = temp.fastPath = new Node(28);
​​​​​​​​temp = temp.addNext(27);
​​​​​​​​temp = temp.addNext(26);
​​​​​​​​temp.next = crossroads;
​​​​}
}