[백준] 19235 모노미노도미노
업데이트:
20년도 상반기 삼성 오전반 기출문제입니다.
문제가 너무 길어서 문제를 천천히 쭉 읽은 뒤 제가 처음에 세운 로직은 다음과 같습니다.
순서는 다음과 같다.
1. 파란색 보드와 초록색 보드 각각에 블록을 바닥으로 떨군다.
2. 블록이 한 줄을 채우는지 체크한다.
2-1. 만약 채워진다면 그 줄을 지워주고 위에서 아래로 떨궈준다.
3. 연한 부분에 블록이 채워졌는지 확인한다.
3-1. 만약 채워졌다면 전부다 한칸 내린다.
4. 아래로 떨군 뒤 2를 한번 더 체크한다. (안채워질때까지)
5. 1부터 반복한다.
블록은
1 : 한개 (x,y)
2 : 1*2 (x,y)(x,y+1) ㅡ
3 : 2*1 (x,y)(x+1,y) ㅣ
처음 문제를 풀면서 가장 큰 문제점은 블록을 구분을 하지 않은 점이였다… 블록이면 1 빈공간이면 0으로 했었고 이렇게 접근한 이유는 문제에서 나온 경계까지 내려간다는 말을 무심코 넘겨서였다. 따라서 그냥 바닥까지 무조건 모든 블록이 내려오는 사태가 발생하였고, 틀렸습니다를 만날 수 있었다.
처음에 접근했던 코드는 다음과 같습니다. (효율적이지 않은 코드여서 엄청 깁니다….)
잘못된 코드 :
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
/*
블록을 구분 안하고 접근하여 잘못된 테케 발생한 코드
*/
int N, Result = 0;
int Green_Board[6][4] = {0,};
int Blue_Board[4][6] = {0,};
void Green_Move(int t, int y) {
int idx = 6;
for (int i = 5; i >= 0; i--) {
if (Green_Board[i][y] == 1)
idx = i;
}
if (t == 1) {
Green_Board[idx-1][y] = 1;
}
else if (t == 2) { // ㅡ
int idx = 6;
for (int i = 5; i >= 0; i--) { // 뻘짓부분..
if (Green_Board[i][y+1] == 1 || Green_Board[i][y] == 1)
idx = i;
}
Green_Board[idx - 1][y] = 1;
Green_Board[idx - 1][y + 1] = 1;
}
else { // ㅣ
Green_Board[idx - 1][y] = 1;
Green_Board[idx - 2][y] = 1;
}
}
void Blue_Move(int t, int x) {
int idx = 6;
for (int i = 5; i >= 0; i--) {
if (Blue_Board[x][i] == 1)
idx = i;
}
if (t == 1) {
Blue_Board[x][idx-1] = 1;
}
else if (t == 2) { // ㅡ
Blue_Board[x][idx-1] = 1;
Blue_Board[x][idx-2] = 1;
}
else { // ㅣ
int idx = 6;
for (int i = 5; i >= 0; i--) {
if (Blue_Board[x][i] == 1 || Blue_Board[x+1][i] == 1)
idx = i;
}
Blue_Board[x+1][idx-1] = 1;
Blue_Board[x][idx-1] = 1;
}
}
bool Green_Chk() { // 1줄 채워지는지 확인 동시에 밀어줌(초록색 보드)
int chk = false;
int idx = 0;
for (int i = 5; i >= 0; i--) {
int cnt = 0;
for (int j = 0; j < 4; j++) {
if (Green_Board[i][j] == 1)
cnt++;
}
if (cnt == 4)
{
chk = true;
idx = i;
break;
}
}
if (chk) {
Result++;
for (int i = 0; i < 4; i++) { // 한줄 날리기
Green_Board[idx][i] = 0;
}
for (int i = 0; i < 4; i++) { // 아래로 몰기
int block_cnt = 0;
for (int j = 5; j >= 0; j--) {
if (Green_Board[j][i] == 1)
block_cnt++;
}
for (int j = 5; j >= 0; j--) {
if (block_cnt > 0) {
Green_Board[j][i] = 1;
block_cnt--;
}
else
Green_Board[j][i] = 0;
}
}
}
return chk;
}
bool Blue_Chk() { // 1줄 채워지는지 확인 동시에 밀어줌(파란색 보드)
int chk = false;
int idx = 0;
for (int i = 5; i >= 0; i--) {
int cnt = 0;
for (int j = 0; j < 4; j++) {
if (Blue_Board[j][i] == 1)
cnt++;
}
if (cnt == 4)
{
chk = true;
idx = i;
break;
}
}
if (chk) {
Result++;
for (int i = 0; i < 4; i++) { // 한줄 날리기
Blue_Board[i][idx] = 0;
}
for (int i = 0; i < 4; i++) { // 오른쪽으로 몰기
int block_cnt = 0;
for (int j = 5; j >= 0; j--) {
if (Blue_Board[i][j] == 1)
block_cnt++;
}
for (int j = 5; j >= 0; j--) {
if (block_cnt > 0) {
Blue_Board[i][j] = 1;
block_cnt--;
}
else
Blue_Board[i][j] = 0;
}
}
}
return chk;
}
void Light_Green() { // 연한부분에 채워지면 밀어주는 곳
int cnt = 0;
for (int i = 0; i < 4; i++) {
if (Green_Board[1][i] == 1) {
cnt++;
break;
}
}
if (cnt == 1) {
for (int i = 0; i < 4; i++) {
if (Green_Board[0][i] == 1) {
cnt++;
break;
}
}
}
if (cnt == 1) { // 한칸 내림
for (int i = 4; i >= 0; i--) {
for (int j = 0; j < 4; j++) {
Green_Board[i + 1][j] = Green_Board[i][j];
}
}
for (int i = 0; i < 4; i++) {
Green_Board[1][i] = 0;
}
}
else if (cnt == 2) { // 두칸 내림
for (int i = 3; i >= 0; i--) {
for (int j = 0; j < 4; j++) {
Green_Board[i + 2][j] = Green_Board[i][j];
}
}
for (int i = 0; i < 4; i++) {
Green_Board[0][i] = 0;
Green_Board[1][i] = 0;
}
}
}
void Light_Blue() { // 연한부분에 채워지면 밀어주는 곳
int cnt = 0;
for (int i = 0; i < 4; i++) {
if (Blue_Board[i][1] == 1) {
cnt++;
break;
}
}
if (cnt == 1) {
for (int i = 0; i < 4; i++) {
if (Blue_Board[i][0] == 1) {
cnt++;
break;
}
}
}
if (cnt == 1) { // 한칸 내림
for (int i = 4; i >= 0; i--) {
for (int j = 0; j < 4; j++) {
Blue_Board[j][i+1] = Blue_Board[j][i];
}
}
for (int i = 0; i < 4; i++) {
Blue_Board[i][1] = 0;
}
}
else if (cnt == 2) { // 두칸 내림
for (int i = 3; i >= 0; i--) {
for (int j = 0; j < 4; j++) {
Blue_Board[j][i+2] = Blue_Board[j][i];
}
}
for (int i = 0; i < 4; i++) {
Blue_Board[i][0] = 0;
Blue_Board[i][1] = 0;
}
}
}
int main() {
cin >> N;
while (N--) {
int t, x, y;
cin >> t >> x >> y;
Green_Move(t, y);
Blue_Move(t, x);
while (Green_Chk()) {
}
while (Blue_Chk()) {
}
Light_Green();
Light_Blue();
}
int Block_Count = 0;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 4; j++) {
if (Green_Board[i][j])
Block_Count++;
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 6; j++) {
if (Blue_Board[i][j])
Block_Count++;
}
}
cout << Result << endl;
cout << Block_Count;
return 0;
}
이후 문제점을 찾았고, 정말… 하기 싫었지만 새롭게 방향을 잡고 푼 결과 맞을 수 있었다. 아 물론 중간에 뻘짓이 하나 있었다. -> 줄이 만약 2줄이 채워지면 2줄을 다 지우고 내렸어야 했는데 한줄을 지우고 내리고 그 담에 또 지우고를 반복하는 바람에 틀린 케이스가 발생하였다. 이런 사소한 실수들이 실제 시험에선 심각하게 다가올 수 있겠다는 생각이 들었고, 실수를 줄이는 연습을 해야 겠다.
Source Code :
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, Result = 0;
int Block_Num = 1;
int Green_Board[6][4] = { 0, };
int Blue_Board[4][6] = { 0, };
void Green_Move(int t, int y) {
int idx = 6;
for (int i = 5; i >= 0; i--) {
if (Green_Board[i][y] >= 1)
idx = i;
}
if (t == 1) {
Green_Board[idx - 1][y] = Block_Num;
}
else if (t == 2) { // ㅡ
int idx = 6;
for (int i = 5; i >= 0; i--) { // 뻘짓부분..
if (Green_Board[i][y + 1] >= 1 || Green_Board[i][y] >= 1)
idx = i;
}
Green_Board[idx - 1][y] = Block_Num;
Green_Board[idx - 1][y + 1] = Block_Num;
}
else { // ㅣ
Green_Board[idx - 1][y] = Block_Num;
Green_Board[idx - 2][y] = Block_Num;
}
}
void Blue_Move(int t, int x) {
int idx = 6;
for (int i = 5; i >= 0; i--) {
if (Blue_Board[x][i] >= 1)
idx = i;
}
if (t == 1) {
Blue_Board[x][idx - 1] = Block_Num;
}
else if (t == 2) { // ㅡ
Blue_Board[x][idx - 1] = Block_Num;
Blue_Board[x][idx - 2] = Block_Num;
}
else { // ㅣ
int idx = 6;
for (int i = 5; i >= 0; i--) {
if (Blue_Board[x][i] >= 1 || Blue_Board[x + 1][i] >= 1)
idx = i;
}
Blue_Board[x + 1][idx - 1] = Block_Num;
Blue_Board[x][idx - 1] = Block_Num;
}
}
void Drop_Green(int idx) { // 경계까지 이동하는 함수
int tmp[6][4] = {0,};
for (int i = 5; i >= idx; i--) { // 아래 부분 저장 (위는 그럼 다 빈공간으로 존재하게됨)
for (int j = 0; j < 4; j++) {
tmp[i][j] = Green_Board[i][j];
}
}
for (int i = idx - 1; i >= 0; i--) {
for (int yidx = 0; yidx < 4; yidx++) {
int number = Green_Board[i][yidx];
if (number == 0) {
continue;
}
else {
int drop_idx = 6;
if (yidx == 0) {
if (Green_Board[i][yidx + 1] == number) { // -
Green_Board[i][yidx] = 0;
Green_Board[i][yidx + 1] = 0;
for (int j = 5; j >= 1; j--) {
if (tmp[j][yidx] != 0 || tmp[j][yidx + 1] != 0) {
drop_idx = j;
}
}
tmp[drop_idx-1][yidx] = number;
tmp[drop_idx-1][yidx + 1] = number;
}
else {
Green_Board[i][yidx] = 0;
for (int j = 5; j >= 1; j--) {
if (tmp[j][yidx] != 0) {
drop_idx = j;
}
}
tmp[drop_idx-1][yidx] = number;
if (i != 0 && Green_Board[i - 1][yidx] == number) {
Green_Board[i - 1][yidx] = 0;
tmp[drop_idx - 2][yidx] = number;
}
}
}
else if (yidx == 1 || yidx == 2) {
if (Green_Board[i][yidx - 1] == number) { // -
Green_Board[i][yidx] = 0;
Green_Board[i][yidx - 1] = 0;
for (int j = 5; j >= 1; j--) {
if (tmp[j][yidx] != 0 || tmp[j][yidx - 1] != 0) {
drop_idx = j;
}
}
tmp[drop_idx-1][yidx] = number;
tmp[drop_idx-1][yidx - 1] = number;
}
else if (Green_Board[i][yidx + 1] == number) { // -
Green_Board[i][yidx] = 0;
Green_Board[i][yidx + 1] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[j][yidx] != 0 || tmp[j][yidx + 1] != 0) {
drop_idx = j;
}
}
tmp[drop_idx-1][yidx] = number;
tmp[drop_idx-1][yidx + 1] = number;
}
else { // 하나 또는 ㅣ
Green_Board[i][yidx] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[j][yidx] != 0) {
drop_idx = j;
}
}
tmp[drop_idx-1][yidx] = number;
if (i != 0 && Green_Board[i - 1][yidx] == number) {
Green_Board[i - 1][yidx] = 0;
tmp[drop_idx - 2][yidx] = number;
}
}
}
else {
if (Green_Board[i][yidx - 1] == number) { // -
Green_Board[i][yidx] = 0;
Green_Board[i][yidx - 1] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[j][yidx] != 0 || tmp[j][yidx - 1] != 0) {
drop_idx = j;
}
}
tmp[drop_idx-1][yidx] = number;
tmp[drop_idx-1][yidx - 1] = number;
}
else {
Green_Board[i][yidx] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[j][yidx] != 0) {
drop_idx = j;
}
}
tmp[drop_idx-1][yidx] = number;
if (i != 0 && Green_Board[i - 1][yidx] == number) {
Green_Board[i - 1][yidx] = 0;
tmp[drop_idx - 2][yidx] = number;
}
}
}
}
}
}
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 4; j++) {
Green_Board[i][j] = tmp[i][j];
}
}
}
void Drop_Blue(int idx) { // 경계까지 이동하는 함수
int tmp[4][6] = {0,};
for (int i = 5; i >= idx; i--) { // 아래 부분 저장 (위는 그럼 다 빈공간으로 존재하게됨)
for (int j = 0; j < 4; j++) {
tmp[j][i] = Blue_Board[j][i];
}
}
for (int i = idx - 1; i >= 0; i--) {
for (int xidx = 0; xidx < 4; xidx++) {
int number = Blue_Board[xidx][i];
if (number == 0) {
continue;
}
else {
int drop_idx = 6;
if (xidx == 0) {
if (Blue_Board[xidx + 1][i] == number) { // l
Blue_Board[xidx][i] = 0;
Blue_Board[xidx + 1][i] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[xidx][j] != 0 || tmp[xidx + 1][j] != 0) {
drop_idx = j;
}
}
drop_idx--;
tmp[xidx][drop_idx] = number;
tmp[xidx + 1][drop_idx] = number;
}
else {
Blue_Board[xidx][i] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[xidx][j] != 0) {
drop_idx = j;
}
}
drop_idx--;
tmp[xidx][drop_idx] = number;
if (i != 0 && Blue_Board[xidx][i - 1] == number) {
Blue_Board[xidx][i - 1] = 0;
tmp[xidx][drop_idx - 1] = number;
}
}
}
else if (xidx == 1 || xidx == 2) {
if (Blue_Board[xidx - 1][i] == number) { // l
Blue_Board[xidx][i] = 0;
Blue_Board[xidx - 1][i] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[xidx][j] != 0 || tmp[xidx - 1][j] != 0) {
drop_idx = j;
}
}
drop_idx--;
tmp[xidx][drop_idx] = number;
tmp[xidx - 1][drop_idx] = number;
}
else if (Blue_Board[xidx + 1][i] == number) { // l
Blue_Board[xidx][i] = 0;
Blue_Board[xidx + 1][i] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[xidx][j] != 0 || tmp[xidx + 1][j] != 0) {
drop_idx = j;
}
}
drop_idx--;
tmp[xidx][drop_idx] = number;
tmp[xidx + 1][drop_idx] = number;
}
else { // 하나 또는 -
Blue_Board[xidx][i] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[xidx][j] != 0) {
drop_idx = j;
}
}
drop_idx--;
tmp[xidx][drop_idx] = number;
if (i != 0 && Blue_Board[xidx][i - 1] == number) {
Blue_Board[xidx][i - 1] = 0;
tmp[xidx][drop_idx - 1] = number;
}
}
}
else {
if (Blue_Board[xidx - 1][i] == number) { // -
Blue_Board[xidx][i] = 0;
Blue_Board[xidx - 1][i] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[xidx][j] != 0 || tmp[xidx - 1][j] != 0) {
drop_idx = j;
}
}
drop_idx--;
tmp[xidx][drop_idx] = number;
tmp[xidx - 1][drop_idx] = number;
}
else {
Blue_Board[xidx][i] = 0;
for (int j = 5; j >= 0; j--) {
if (tmp[xidx][j] != 0) {
drop_idx = j;
}
}
drop_idx--;
tmp[xidx][drop_idx] = number;
if (i != 0 && Blue_Board[xidx][i - 1] == number) {
Blue_Board[xidx][i - 1] = 0;
tmp[xidx][drop_idx - 1] = number;
}
}
}
}
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 6; j++) {
Blue_Board[i][j] = tmp[i][j];
}
}
}
bool Green_Chk() { // 1줄 채워지는지 확인 동시에 밀어줌(초록색 보드) -> 라고 처음에 생각했으나 그냥 줄 채워지면 바로 다 없애고 밀어줬어야 했다...
int chk = false;
int idx = 0;
for (int i = 5; i >= 2; i--) {
int cnt = 0;
for (int j = 0; j < 4; j++) {
if (Green_Board[i][j] >= 1)
cnt++;
}
if (cnt == 4)
{
chk = true;
idx = i;
Result++;
for (int i = 0; i < 4; i++) { // 한줄 날리기
Green_Board[idx][i] = 0;
}
}
}
if (chk) {
Drop_Green(idx);
}
return chk;
}
bool Blue_Chk() { // 1줄 채워지는지 확인 동시에 밀어줌(파란색 보드)
int chk = false;
int idx = 0;
for (int i = 5; i >= 2; i--) {
int cnt = 0;
for (int j = 0; j < 4; j++) {
if (Blue_Board[j][i] >= 1)
cnt++;
}
if (cnt == 4)
{
chk = true;
idx = i;
Result++;
for (int i = 0; i < 4; i++) { // 한줄 날리기
Blue_Board[i][idx] = 0;
}
}
}
if (chk) {
Drop_Blue(idx);
}
return chk;
}
void Light_Green() { // 연한부분에 채워지면 밀어주는 곳
int cnt = 0;
for (int i = 0; i < 4; i++) {
if (Green_Board[1][i] > 0) {
cnt++;
break;
}
}
if (cnt == 1) {
for (int i = 0; i < 4; i++) {
if (Green_Board[0][i] > 0) {
cnt++;
break;
}
}
}
if (cnt == 1) { // 한칸 내림
for (int i = 4; i >= 0; i--) {
for (int j = 0; j < 4; j++) {
Green_Board[i + 1][j] = Green_Board[i][j];
}
}
for (int i = 0; i < 4; i++) {
Green_Board[1][i] = 0;
}
Drop_Green(5);
}
else if (cnt == 2) { // 두칸 내림
for (int i = 3; i >= 0; i--) {
for (int j = 0; j < 4; j++) {
Green_Board[i + 2][j] = Green_Board[i][j];
}
}
for (int i = 0; i < 4; i++) {
Green_Board[0][i] = 0;
Green_Board[1][i] = 0;
}
Drop_Green(5);
}
}
void Light_Blue() { // 연한부분에 채워지면 밀어주는 곳
int cnt = 0;
for (int i = 0; i < 4; i++) {
if (Blue_Board[i][1] > 0) {
cnt++;
break;
}
}
if (cnt == 1) {
for (int i = 0; i < 4; i++) {
if (Blue_Board[i][0] > 0) {
cnt++;
break;
}
}
}
if (cnt == 1) { // 한칸 내림
for (int i = 4; i >= 0; i--) {
for (int j = 0; j < 4; j++) {
Blue_Board[j][i + 1] = Blue_Board[j][i];
}
}
for (int i = 0; i < 4; i++) {
Blue_Board[i][1] = 0;
}
Drop_Blue(5);
}
else if (cnt == 2) { // 두칸 내림
for (int i = 3; i >= 0; i--) {
for (int j = 0; j < 4; j++) {
Blue_Board[j][i + 2] = Blue_Board[j][i];
}
}
for (int i = 0; i < 4; i++) {
Blue_Board[i][0] = 0;
Blue_Board[i][1] = 0;
}
Drop_Blue(5);
}
}
int main() {
cin >> N;
while (N--) {
int t, x, y;
cin >> t >> x >> y;
Green_Move(t, y);
Blue_Move(t, x);
Block_Num++;
while (Green_Chk()) {
}
while (Blue_Chk()) {
}
Light_Green();
Light_Blue();
while (Green_Chk()) {
}
while (Blue_Chk()) {
}
}
int Block_Count = 0;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 4; j++) {
if (Green_Board[i][j])
Block_Count++;
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 6; j++) {
if (Blue_Board[i][j])
Block_Count++;
}
}
cout << Result << endl;
cout << Block_Count;
return 0;
}
Summary
- 실제로 이런 문제를 시험장에서 만난다면 과연 난 풀수있을까…라는 의문이 들었다.
- 좀 더 실수를 줄이기 위해 귀찮거나 복잡한 문제들도 도전해야겠다.
- 코드가 많이 지저분하니 좀 깨끗하게 수정하자..
소스코드
이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이
댓글남기기