알고리즘 문제 해결(PS)/[백준]

[백준] 17825번 주사위 윷놀이 (자바 풀이)

연구소장 J 2022. 3. 25. 09:43

문제

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

 

17825번: 주사위 윷놀이

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

www.acmicpc.net

 

풀이

너무 어려운 문제였다. 

 

이 문제는 보드판을 연결 리스트로 표현해서 풀면 해결할 수 있다. 

class Node{
	int val;
	boolean isEmpty, isFinish;
	Node next, fastPath;
	
	Node(int val){
		this.val = val;
		this.isEmpty = true;
	}
	
	// 노드 연결
	Node addNext(int value) {
		Node nextNode = new Node(value);
		this.next = nextNode;
		return nextNode;
	}
	
	// 시작지점부터 탐색해가며 특정 노드를 찾는 메서드
	static Node getNode(Node start, int target) {
		Node temp = start;
		while(true) {
			if(temp == null) {
				return null;
			}
			if(temp.val == target) {
				return temp;
			}
			temp = temp.next;
		}
	}
}

위와 같은 Node 클래스를 만들어서 연결 리스트로 사용하면, next로 다음 칸을 연결하고 fastPath로 지름길을 나타낼 수 있다. 

 

또한, 말들의 이동을 조합하는 것은 순열을 이용해서 해결하면 된다. 총 10번의 말의 이동이 있기 때문에

1,2,3,4를 중복을 허용해 10개의 원소를 순열로 만들어내면 된다.

 

자세한 내용은 코드를 참고하자.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Baekjoon_17825 {
    static int[] dice, order; // 주사위, 배치순서
    static Node[] horse; // 4개의 말
    static Node start; // 시작지점
    static int answer = Integer.MIN_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        dice = new int[11];
        order = new int[11];
        horse = new Node[5];
        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) {
        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.val;
            }
        } // 게임종료
        
        // 다음 게임을 위해 말 위치 초기화 
        for (int i=1; i<=4; i++) {
            horse[i].isEmpty = true;
        }
        return score;
    }
    
    private static void init() {
        start = new Node(0); // 시작위치와 점수
 
        Node temp = start;
        for(int i = 2 ; i <= 40 ; i += 2) {    // 바깥쪽 경로 설정
            temp = temp.addNext(i);
        }
        
        // 도착지점
        Node end = temp.addNext(0);
        end.isFinish = true;
        end.next = end; // 자기 자신 포인트 -> NPE 방지
        
        // 가운데 교차점(val = 25)
        Node crossroads = new Node(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;
    }
}
 
class Node{
    int val;
    boolean isEmpty, isFinish;
    Node next, fastPath;
    
    Node(int val){
        this.val = val;
        this.isEmpty = true;
    }
    
    // 노드 연결
    Node addNext(int value) {
        Node nextNode = new Node(value);
        this.next = nextNode;
        return nextNode;
    }
    
    // 시작지점부터 탐색해가며 특정 노드를 찾는 메서드
    static Node getNode(Node start, int target) {
        Node temp = start;
        while(true) {
            if(temp == null) {
                return null;
            }
            if(temp.val == target) {
                return temp;
            }
            temp = temp.next;
        }
    }
}
cs
반응형