알고리즘/SW Expert Academy
5650.핀볼 게임
IMyoungho
2020. 6. 14. 13:40
이번에 풀어볼 문제는 핀볼게임이다. 정답률은 31%정도인데 나의 체감은 60%정도가 맞지 않나싶다.
오히려 5656번 벽돌깨기가 체감난이도가 더 높았다. 근데 그건.. 정답률이 60%... 여튼 한 번에 풀어서 다행이다.
톱니봐퀴나 핀볼게임이나 공통점은 문제를 풀면서 딱히 큰 예외를 신경쓰지 않아도 될 것같다는 느낌과
정확하게만 구현하면 딱히 큰 예외가 없어서 한 번에 정답이 맞겠다는 느낌이 오는 문제였다는 것이다.
내 코드가 좋다는 것은 아니지만 그냥 하라는대로 하니까 풀린 문제이다.
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
설명은 딱히 없다. 풀이 방식은 다음과 같다.
1. 빈 칸에 핀볼이 떨어져서 상, 하, 좌, 우로 움직인다 => 즉, 빈칸에 다 들어가고 4방향으로 탐색하는 경우의 수를 다해봐야한다.
2. 그 다음 부터는 그냥 벽돌모양과 벽에 부딪히는 것에 대해 똑같이 구현만 해주면 된다.
그래서 나는 현재 방향을 변수로 처리해서 방향이 바뀔 때마다 해당 변수 값만 바꿔주면서 문제를 풀었다..
웜홀의 경우는 deque로 짝을 지어줘서 2개가 1쌍이므로 현재 좌표와 다른 웜홀 좌표를 사용했다.
< Code 설명 >
|
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
|
#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <algorithm>
#include <string.h>
#define MAX 101
using namespace std;
int T, N;
int map[MAX][MAX];
int dx[4] = { 0, -1, 0, 1 }; // 좌, 상, 우 하
int dy[4] = { -1, 0, 1, 0 };
deque<int>x_mov;
deque<int>y_mov;
deque<pair<int, int>>hole1;
deque<pair<int, int>>hole2;
deque<pair<int, int>>hole3;
deque<pair<int, int>>hole4;
deque<pair<int, int>>hole5;
void dir_set(){ // 방향 deque 저장
for (int i = 0; i < 4; i++){
x_mov.push_back(dx[i]);
y_mov.push_back(dy[i]);
}
}
void dir_modi(){ // 시작 방향 변경 함수(상하좌우 4방향)
x_mov.push_back(x_mov.front());
x_mov.pop_front();
y_mov.push_back(x_mov.front());
y_mov.pop_front();
}
bool crash_wall(int x, int y){
if (x < 0 || y < 0 || x >= N || y >= N) // 맵 벽에 부딪히는 경우
return true;
return false;
}
void hole_change(int num){ // 자기 짝에 맞는 웜홀로 움직이게하는 함수
switch (num)
{
case 6:
hole1.push_back(hole1.front());
hole1.pop_front();
break;
case 7:
hole2.push_back(hole2.front());
hole2.pop_front();
break;
case 8:
hole3.push_back(hole3.front());
hole3.pop_front();
break;
case 9:
hole4.push_back(hole4.front());
hole4.pop_front();
break;
case 10:
hole5.push_back(hole5.front());
hole5.pop_front();
break;
}
}
int play(int x, int y){
int num = 0;
int first_x = x;
int first_y = y;
int max_point = 0;
for (int t = 0; t < 4; t++){ //4방향 탐색을 위한 반복문
int point = 0;
int cur_tmp_x = x_mov[t];
int cur_tmp_y = y_mov[t];
x = first_x;
y = first_y;
while (true){ //방향 하나당 끝날때까지 진행
int ax = x + cur_tmp_x; // 해당 방향으로 전진
int ay = y + cur_tmp_y; // 해당 방향으로 전진
if ((ax == first_x && ay == first_y) || map[ax][ay] == -1){
// 시작점을 돌아오거나 블랙홀을 만나면 종료
if (point > max_point) // 최대 포인트 저장
max_point = point;
break;
}
if (crash_wall(ax,ay) || map[ax][ay] == 5) // 맵 벽에 부딪히는 경우, 5번에 부딪히거나
{
// 부딪힌 방향의 반대로 감
if (cur_tmp_x == 1 && cur_tmp_y == 0)
cur_tmp_x = -1;
else if (cur_tmp_x == -1 && cur_tmp_y == 0)
cur_tmp_x = 1;
else if (cur_tmp_x == 0 && cur_tmp_y == 1)
cur_tmp_y = -1;
else if (cur_tmp_x == 0 && cur_tmp_y == -1)
cur_tmp_y = 1;
point += 1; // 벽에 부딪혔으니 포인트 +1;
}
// 웜홀에 들어가는 경우
else if (map[ax][ay]>5){
if (map[ax][ay] == 6){
if (ax == hole1.front().first && ay == hole1.front().second)
hole_change(6);
ax = hole1.front().first;
ay = hole1.front().second;
}
else if (map[ax][ay] == 7){
if (ax == hole2.front().first && ay == hole2.front().second)
hole_change(7);
ax = hole2.front().first;
ay = hole2.front().second;
}
else if (map[ax][ay] == 8){
if (ax == hole3.front().first && ay == hole3.front().second)
hole_change(8);
ax = hole3.front().first;
ay = hole3.front().second;
}
else if (map[ax][ay] == 9){
if (ax == hole4.front().first && ay == hole4.front().second)
hole_change(9);
ax = hole4.front().first;
ay = hole4.front().second;
}
else if (map[ax][ay] == 10){
if (ax == hole5.front().first && ay == hole5.front().second)
hole_change(10);
ax = hole5.front().first;
ay = hole5.front().second;
}
}
// 세모 모양 중 평면에 부딪히는 경우
else if ((map[ax][ay] == 1 || map[ax][ay] == 2) && (cur_tmp_x == 0 && cur_tmp_y == 1)){
cur_tmp_x = 0;
cur_tmp_y = -1;
// 0, -1
point += 1; // 벽에 부딪혔으니 포인트 +1;
}
else if ((map[ax][ay] == 1 || map[ax][ay] == 4) && (cur_tmp_x == -1 && cur_tmp_y == 0)){
cur_tmp_x = 1;
cur_tmp_y = 0;
// 1, 0
point += 1; // 벽에 부딪혔으니 포인트 +1;
}
else if ((map[ax][ay] == 2 || map[ax][ay] == 3) && (cur_tmp_x == 1 && cur_tmp_y == 0)){
cur_tmp_x = -1;
cur_tmp_y = 0;
// -1, 0
point += 1; // 벽에 부딪혔으니 포인트 +1;
}
else if ((map[ax][ay] == 3 || map[ax][ay] == 4) && (cur_tmp_x == 0 && cur_tmp_y == -1)){
cur_tmp_x = 0;
cur_tmp_y = 1;
// 0, 1
point += 1; // 벽에 부딪혔으니 포인트 +1;
}
// 세모모양 중 대각벽에 부딪히는 경우
else if ((map[ax][ay] == 1 || map[ax][ay] == 2) && (cur_tmp_x == 1 || cur_tmp_x == -1) && cur_tmp_y == 0){ // 상, 하 => 우
cur_tmp_x = 0;
cur_tmp_y = 1;
// 0, 1
point += 1; // 벽에 부딪혔으니 포인트 +1;
}
else if ((map[ax][ay] == 1 || map[ax][ay] == 4) && cur_tmp_x == 0 && (cur_tmp_y == -1 || cur_tmp_y == 1)){ // 좌, 우 => 상
cur_tmp_x = -1;
cur_tmp_y = 0;
// -1, 0
point += 1; // 벽에 부딪혔으니 포인트 +1;
}
else if ((map[ax][ay] == 2 || map[ax][ay] == 3) && cur_tmp_x == 0 && (cur_tmp_y == -1 || cur_tmp_y == 1)){ // 좌, 우 => 하
cur_tmp_x = 1;
cur_tmp_y = 0;
//1, 0
point += 1; // 벽에 부딪혔으니 포인트 +1;
}
else if ((map[ax][ay] == 3 || map[ax][ay] == 4) && (cur_tmp_x == 1 || cur_tmp_x == -1) && cur_tmp_y == 0){// 상, 하 => 좌
cur_tmp_x = 0;
cur_tmp_y = -1;
// 0, -1
point += 1; // 벽에 부딪혔으니 포인트 +1;
}
x = ax, y = ay;
}
}
return max_point;
}
void reset(){
memset(map, 0, sizeof(map));
x_mov.clear();
y_mov.clear();
hole1.clear();
hole2.clear();
hole3.clear();
hole4.clear();
hole5.clear();
}
int main() {
freopen("5650.txt", "r", stdin);
cin >> T;
for (int z = 1; z <= T; z++){
reset();
deque<pair<int, int>>start;
cin >> N;
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cin >> map[i][j];
if (map[i][j]==0)
start.push_back(make_pair(i, j));
else if (map[i][j] == 6)
hole1.push_back(make_pair(i, j));
else if (map[i][j] == 7)
hole2.push_back(make_pair(i, j));
else if (map[i][j] == 8)
hole3.push_back(make_pair(i, j));
else if (map[i][j] == 9)
hole4.push_back(make_pair(i, j));
else if (map[i][j] == 10)
hole5.push_back(make_pair(i, j));
}
}
int start_pos = start.size(); // 공을 놓을 수 있는 위치
dir_set();
int answer = -777;
for (int i = 0; i < start_pos; i++){
answer = max(answer,play(start.front().first, start.front().second));
start.pop_front();
}
cout << "#" << z << " " << answer << "\n";
}
return 0;
}
|
cs |
# 무식하게 푼 것 같지만... 풀긴 풀었으니까.. 조금 더 보완하면 되지 않을까??
코드는 보다시피 줄일 수 있다. 보완할 점은 줄일 수 있는 코드를 줄이면서 코드를 짤 수 있는 설계능력인 것 같다..
< Code 설명 - 수정 >
|
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
|
#pragma warning(disable:4996) #include <iostream>
#include <deque>
#include <algorithm>
#include <string.h>
#define MAX 101
using namespace std;
int T, N, ans;
int map[MAX][MAX];
int dx[5] = { 0, -1, 1, 0, 0 }; // 상하좌우
int dy[5] = { 0, 0, 0, -1, 1 };
struct holl{
deque<pair<int, int>>d;
};
holl worm[11];
int reverse(int dir){ // 벽면을 만났을 때 -> 방향리턴
if (dir == 1)
return 2;
else if (dir == 2)
return 1;
else if (dir == 3)
return 4;
else if (dir == 4)
return 3;
}
int corner(int block, int dir){ // 대각면을 만났을때 -> 방향리턴
if (block == 1){
if (dir == 2)
return 4;
else if (dir == 3)
return 1;
else if (dir == 4 || dir == 1)
return reverse(dir);
}
else if (block == 2){
if (dir == 1)
return 4;
else if (dir == 3)
return 2;
else if (dir == 4 || dir == 2)
return reverse(dir);
}
else if (block == 3){
if (dir == 1)
return 3;
else if (dir == 4)
return 2;
else if (dir == 2 || dir == 3)
return reverse(dir);
}
else if (block == 4){
if (dir == 2)
return 3;
else if (dir == 4)
return 1;
else if (dir == 1 || dir == 3)
return reverse(dir);
}
else if (block == 5)
return reverse(dir);
else
return dir;
}
void search(int a, int b, int s_dir){
int x, y, start_x, start_y, cnt, dir;
start_x = x = a;
start_y = y = b;
dir = s_dir;
cnt = 0;
bool flag;
while (true){
flag = false;
int ax = x + dx[dir];
int ay = y + dy[dir];
if ((ax == start_x && ay == start_y) || map[ax][ay] == -1){ // 시작좌표거나 블랙홀이면
ans = max(ans, cnt);
break;
}
if (ax < 0 || ay < 0 || ax >= N || ay >= N){ // 테두리 벽을 만나면
dir = reverse(dir);
cnt++;
}
else if (map[ax][ay] <= 5 && map[ax][ay] >= 1){ // 블록을 만나면
dir = corner(map[ax][ay], dir);
cnt++;
}
else if (map[ax][ay] >= 6){ // 웜홀을 만나면
for (int i = 0; i < 2; i++){
if (worm[map[ax][ay]].d[i].first != ax || worm[map[ax][ay]].d[i].second != ay){
x = worm[map[ax][ay]].d[i].first;
y = worm[map[ax][ay]].d[i].second;
flag = true;
break;
}
}
}
if (!flag){
x = ax;
y = ay;
}
}
}
void init(){
memset(map, 0, sizeof(map));
for (int i = 0; i <= 10; i++)
worm[i].d.clear();
ans = 0;
}
int main(){
freopen("5650.txt", "r", stdin);
cin >> T;
for (int z = 1; z <= T; z++){
cin >> N;
init();
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cin >> map[i][j];
if (map[i][j] >= 6)
worm[map[i][j]].d.push_back(make_pair(i, j));
}
}
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
for (int dir = 1; dir <= 4; dir++){
if (map[i][j] == 0){
search(i, j, dir);
}
}
}
}
cout << "#" << z << " " << ans << endl;
}
return 0;
}
|
cs |
반응형