BOJ 17825 주사위 윷놀이

작성일 | In |

Problem : 주사위 윷놀이

유형 : 구현

문제 해석 (5)

  • 말 4개가 있다
  • 주사위 10개의 결과를 이미 알고 있다
  • 말을 조건에 맞춰서 움직이고, 최대 점수를 구하라.

문제 재해석

  • 주어진 그대로 구현하면 되는 구현 문제이다

해결 전략 (15)

  • 어느 위치에서 갈 수 있는 위치는 정해져 있다.
  • 예를 들어 점수 10이 적혀있는 위치에서 갈 수 있는 곳은 13, 16 , 19, 25… 로 고정 되어있다.
  • 데이터 테이블을 미리 만들어 두고 해결한다.
  • 말들이 주사위 점수에 따라 이동 할 수 있는 모든 조합을 구해본다.

구현, 설계 (40)

image

  • 각 좌표에서 갈 수 있는 곳 이상을 가려고 하는 경우 도착으로 가는 것으로 처리했다.
  • DFS로 모든 말의 조합을 만들었다.
  • 10번을 움직일 수 없다면 있을 수 없는 경우이므로, 0을 리턴 했다.

디버깅 (60)

  • 데이터 테이블 세팅 실수를 했다.
  • 점수 초기 세팅 실수를 했다.
  • 말이 겹치는 경우 게임을 종료시키지 않는 실수를 했다.
  • 말을 움직인 경우, 말의 위치 정보를 갱신하지 않는 실수를 했다.

주의할 점

  • 말이 겹치는 경우가 발생할 경우. 해당 조합으로 진행하던 게임은 종료해야 한다.
    • 턴을 무효화 하는 것이 아니다. 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
#include <bits/stdc++.h>
using namespace std;

int score[33] = { 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,13,16,19,22,24,28,27,26,25,30,35};
bool visit[32];

int knight_spot[4];
int dice[10];
int order[10];

const int A = 0, B = 1, C = 2, D = 3;
const int fin = 100;

int answer;

vector<int>table[41] = {
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},
{0,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},
{0,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},
{0,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},
{0,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},

{0,21,22,23,29,30,31,20},

{0,7,8,9,10,11,12,13,14,15,16,17,18,19,20},
{0,8,9,10,11,12,13,14,15,16,17,18,19,20},
{0,9,10,11,12,13,14,15,16,17,18,19,20},
{0,10,11,12,13,14,15,16,17,18,19,20},

{0,24,25,29,30,31,20},

{0,12,13,14,15,16,17,18,19,20},
{0,13,14,15,16,17,18,19,20},
{0,14,15,16,17,18,19,20},
{0,15,16,17,18,19,20},

{0,26,27,28,29,30,31,20},

{0,17,18,19,20},
{0,18,19,20},
{0,19,20},
{0,20},

{0},

{0,22,23,29,30,31,20},
{0,23,29,30,31,20},
{0,29,30,31,20},

{0,25,29,30,31,20},
{0,29,30,31,20},

{0,27,28,29,30,31,20},
{0,28,29,30,31,20},
{0,29,30,31,20},

{0,30,31,20},
{0,31,20},
{0,20},

};

int Move() {
	int sum = 0;

	for (int i = 0; i < 10; ++i) {
		int knight = order[i];
		int cur_spot = knight_spot[knight];
		int move_dist = dice[i];

		if (cur_spot == fin) return 0;

		if (move_dist >= (int)table[cur_spot].size()) {
			visit[cur_spot] = false;
			knight_spot[knight] = fin;
		}
		else {
			int nxt_spot = table[cur_spot][move_dist];

			if (visit[nxt_spot]) return 0;
			visit[nxt_spot] = true;
			knight_spot[knight] = nxt_spot;

			sum += score[nxt_spot];
			visit[cur_spot] = false;
		}

	}
	return sum;
}

void Dfs(int dice_n) {

	if (dice_n == 10) {

		memset(visit, false, sizeof(visit));
		memset(knight_spot, false, sizeof(knight_spot));

		answer = max(answer, Move());

		return;
	}

	order[dice_n] = A;
	Dfs(dice_n + 1);

	order[dice_n] = B;
	Dfs(dice_n + 1);

	order[dice_n] = C;
	Dfs(dice_n + 1);

	order[dice_n] = D;
	Dfs(dice_n + 1);

}

void Solve() {
    Dfs(0);

	cout << answer << "\n";
}

void Input() {
    for (int i = 0; i < 10; ++i) {
        cin >> dice[i];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

	Input();
	Solve();


    return 0;
}

피드백

  • 점수 초기 세팅을 잘못해서 틀렸다.
  • 꼼꼼함이 필요할 것 같다.
  • 설명에 중요한 내용이 드러나지 않게 있을 수 있다.
  • 문제의 조건은 진짜 곰곰히 생각해보자.