https://www.acmicpc.net/problem/3019
3019번: 테트리스
문제 테트리스는 C열 필드위에서 플레이하는 유명한 게임이다. 필드의 행의 수는 무한하다. 한 번 움직일 때, 아래와 같은 일곱가지 블록 중 하나를 필드에 떨어뜨릴 수 있다. 블록을 떨어뜨리기 전에, 플레이어는 블록을 90, 180, 270도 회전시키거나 좌우로 움직일 수 있다. 이때, 블록이 필드를 벗어나지 않으면 된다. 블록을 필드의 바닥이나 이미 채워져있는 칸의 위에 놓여지게 된다. 창영이가 하고있는 테트리스는 일반적인 테트리스와 약간 규칙이 다르다.
www.acmicpc.net
|
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
|
#define _CRT_SECURE_NO_WARNINGS
#define CSIZE 108
#define PSIZE 8
#include<stdio.h>
#include<iostream>
using namespace std;
int block[PSIZE][4][4][4]{
{
},
{
{///1
{1,0,0,0},
{1,0,0,0},
{1,0,0,0},
{1,0,0,0}
},
{
{1,1,1,1},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}
},
},
{
{//2
{1,1,0,0},
{1,1,0,0},
{0,0,0,0},
{0,0,0,0}
},
},
{
{//3
{0,1,1,0},
{1,1,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},
{1,1,0,0},
{0,1,0,0},
{0,0,0,0}
},
},
{
{//4
{1,1,0,0},
{0,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{0,1,0,0},
{1,1,0,0},
{1,0,0,0},
{0,0,0,0}
},
},
{
{//5
{0,1,0,0},
{1,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},
{1,1,0,0},
{1,0,0,0},
{0,0,0,0}
},
{
{0,1,0,0},
{1,1,0,0},
{0,1,0,0},
{0,0,0,0}
},
{
{1,1,1,0},
{0,1,0,0},
{0,0,0,0},
{0,0,0,0}
},
},
{
{//6
{0,0,1,0},
{1,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},
{1,0,0,0},
{1,1,0,0},
{0,0,0,0}
},
{
{1,1,1,0},
{1,0,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,0,0},
{0,1,0,0},
{0,1,0,0},
{0,0,0,0}
},
},
{
{//7
{1,0,0,0},
{1,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,0,0},
{1,0,0,0},
{1,0,0,0},
{0,0,0,0}
},
{
{1,1,1,0},
{0,0,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{0,1,0,0},
{0,1,0,0},
{1,1,0,0},
{0,0,0,0}
},
}
};
int blockCnt[PSIZE] = { 0,2,1,2,2,4,4,4 };
int N, P;
int input[CSIZE][CSIZE];
int ret;
void init() {
cin >> N >> P;
for (int i = 0; i < N; i++) {
int cnt;
cin >> cnt;
for (int j = CSIZE-5, k = 0; k < cnt; k++, j--) {
input[j][i] = 1;
}
}
}
void copy1(int cinput[CSIZE][CSIZE],int input[CSIZE][CSIZE]) {
for (int i = 0; i < CSIZE-4; i++) {
for (int j = 0; j < N; j++) {
cinput[i][j] = input[i][j];
}
}
}
void chkCnt() {
for (int x = 0; x < N; x++) {
int flag = 0;
for (int y = CSIZE-5; y >= 0; y--) {
if (input[y][x] == 0&&flag==0) {
flag = 1;
}
if (flag == 1 && input[y][x] == 1) return;
}
}
ret++;
}
void gamePlay() {
for (int k = 0; k < blockCnt[P]; k++) {
for (int x = 0; x < N; x++) {
for (int y = CSIZE-5; y >= 0; y--) {
int cinput[CSIZE][CSIZE] = { 0, };
copy1(cinput, input);
int flag = 0;
for (int ky = 0; ky < 4; ky++) {
for (int kx = 0; kx < 4; kx++) {
int ny = y + ky;
int nx = x + kx;
if ((input[ny][nx] ==1&& block[P][k][ky][kx] == 1)||( block[P][k][ky][kx] == 1 && (ny < 0 || ny >= CSIZE-4 || nx < 0 || nx >= N))) {
flag = 1;
break;
}
else {
if (block[P][k][ky][kx] == 1) input[ny][nx]++;
}
}
if (flag)break;
}
if (flag == 0) {
chkCnt();
copy1(input, cinput);
break;
}
copy1(input, cinput);
}
}
}
}
int main(void) {
init();
gamePlay();
cout << ret << endl;
return 0;
}
|
실질적으로 동작하는 부분은 적은데 전체 나오는 블록을 저장을 하려다 보니 소스가 어마어마하게 기네요.
일단 이문제의 백퍼 맞는 풀이는 아니지만 저는 이런문제가 나오면 우선 각 블록을 저장를 먼저합니다.
우선 블록이 최대 들어갈수 있는 배열방은 4 * 4 이므로 이런식으로 우선 그리고
이것을 전부 4차원배열을 이용해서 담았습니다. block[각블록의 유형] [각블록의 다른모양] [4] [4];
이렇게 4차원배열을 이용해서 담았고 문제 풀이방식은 제일 끝부분부터 블록을 올릴수 있는 위치에 도달하면
빈공간이 생기는지안생기는지 확인해서 안생기면 카운트해주는 방식을 사용했습니다.
이렇게 제일 아래 부분부터 블록의 범위가 맵의 범위를 벗어나지 않고 또 다른 블록과 겹쳐지지 않는 구간을
찾고 그위치에서
제일 왼쪽 끝모서리부터 시작해서 위에 올라가면서 공백을 만나면 일단flag==1로 바뀌고
이때 이후에 블록이 그 윗공간에 있으면 안되기때문에 있으면 false 반환
없으면 카운터가 세어지는것입니다. 정말 단순하지 않나요?
이렇게 하면 풀리는데 저는 다 풀고 실수 한것이 위의 공간은 무한이고 입력으로 처음 들어오는 블록은 최대 100일때를
제대로 생각을 안해서 틀리더라구요. 그래서 높이를 더 확장 시킴으로서 문제를 풀이를 성공했습니다.
여러분들은 저같은 실수 안하실꺼라 생각합니다. 저만의 실수라 ㅜㅜㅜ 아직 더 분발해야겠습니다.
대게 테트리스 같은 문제는 여러 코딩 테스트에 많이 나오더라구요 그래서 좀 알아두시면 도움될것이라고 생각합니다.
오늘은 여기까지이고 여러분들도 즐거운 코딩하세요.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 2422 한윤정이 이탈리아에 가서 아이스크림을 (0) | 2019.10.07 |
|---|---|
| 백준 1107 리모컨 (0) | 2019.10.04 |
| 백준 3568 iSharp (0) | 2019.10.04 |
| 백준 14226 이모티콘 (0) | 2019.10.03 |
| 백준 13549 숨바꼭질3 (0) | 2019.10.03 |
댓글