1. 문제 링크
2. 풀이
특별한 알고리즘은 요구하지 않고
오로지 구현력으로 승부를 보는 문제입니다.
이런 빡구현 유형은 문제를 단순화하는 부분부터 시작합니다.
1. 단순화 하기(파란색 보드도 초록색 보드처럼 생각)
문제에서는 초록색 보드와 파란색 보드 둘 다 신경써야 합니다.
같은 로직인데 방향만 다르다고 따로 만드는 짓은 비효율적이고 버그가 나올 확률도 높습니다.
초록색 보드의 로직은 잘 짜놓고 파란색 보드의 로직은 틀리게 짜면 너무 아깝잖아요?
그래서 파란색 보드도 초록색 보드처럼 생각하면 더 효율적으로 문제를 풀 수 있습니다.
초록색 보드
파란색 보드
파란색 보드도 90도 돌린 다음 옆으로 뒤집은 형태라 생각합시다.
그러면 블럭의 좌표 (y, x)가 주어졌을 때
파란색 입장에서는 (x, y)로 해석하기만 하면 됩니다.
2. 블럭 만들기 + 블럭 떨구기
int my[3] = { 0, 0, 1 };
int mx[3] = { 0, 1, 0 };
// 블럭 떨구는 함수
void dropBlock(int board, int y1, int x1, int y2, int x2, int block) {
while (y1 < ROW && y2 < ROW && boards[board][y1][x1] == 0 && boards[board][y2][x2] == 0) {
y1++;
y2++;
}
boards[board][y1 - 1][x1] = boards[board][y2 - 1][x2] = block;
}
cin >> t >> yy1 >> xx1;
yy2 = yy1 + my[t - 1];
xx2 = xx1 + mx[t - 1];
dropBlock(GREEN, yy1, xx1, yy2, xx2, t == 3 ? 1 : t);
dropBlock(BLUE, yy1, xx1, yy2, xx2, t == 3 ? 1 : t);my, mxt에 따라서 짝꿍 블럭 좌표를 만들어줄 때 쓰이는 배열입니다.
t == 1일 땐 '.' 모양이니y + 0, x + 0
t == 2일 땐 '--' 모양이니y + 0, x + 1
t == 3일 땐 '|' 모양이니y + 1, x + 0
dropBlock함수- 보드의 맨 밑에 닿거나, 다음 좌표에 다른 블럭이 있을 때까지 내려간 다음,
그 위치에 블럭을 놓는 함수입니다. - 6번째 인자인
int block은 블럭을 내릴 때 쓰이는 값인데요,
이건 밑에서 더 자세하게 설명하겠습니다.
- 보드의 맨 밑에 닿거나, 다음 좌표에 다른 블럭이 있을 때까지 내려간 다음,
3. 더 이상 삭제할 행이 없을 때까지 행 삭제
// 더 이상 삭제할 행이 없을 때까지 행 삭제하는 함수
void deleteRowUntillAble(int board) {
while (1) {
int maxDeletedRow = -1;
// 행 삭제
for (int r = 4; r < ROW; r++) {
int isDelete = 1;
for (int c = 0; c < COL; c++) {
if (boards[board][r][c] == 0) {
isDelete = 0;
break;
}
}
if (!isDelete) continue;
deleteRow(board, r); // 행 삭제
score++; // 점수 증가
maxDeletedRow = r;
}
if (maxDeletedRow == -1) break;
downBlock(board, maxDeletedRow - 1);
}
}deleteRow는 단순히
// 행 삭제
void deleteRow(int board, int r) {
for (int c = 0; c < COL; c++) {
boards[board][r][c] = 0;
}
}한 행을 삭제하는 함수입니다.
주목할 부분은 downBlock함수인데요, 보드에 행들이 삭제되고난 후,
블럭 단위로 블럭이 보드 밑으로 떨어지는 로직을 구현한 함수입니다.
dropBlock함수의 6번째 인자인 int block이 필요했던 이유가
이 부분을 구현하기 위해서입니다.
블럭 단위로 내리기 위해서는 결국 '--' 모양만 신경쓰면 됩니다.
나머지 '.', '|' 모양은 밑에 블럭이 없을 때까지 내리면 됩니다. (마이 웨이)
하지만 '--' 요 녀석은 다릅니다. 아주 까다로운 녀석이죠.
왼쪽 부분 밑에는 블럭이 없어도, 오른쪽 부분 밑에는 블록이 있다면
더 내려가지 않고 멈춰야 합니다.
왜냐하면 둘은 세트이기 때문에
블록 단위로 내려줘야하는 이 문제의 조건에 부합하려면 두 부분 다 신경써야 합니다.
그래서 '.', '|'은 int block을 1로 설정해줬고,
'--' 이 녀석은 까다로운 녀석이란 뜻으로 int block을 2로 설정했습니다.
그리고 block을 떨굴 때 초록색 보드인지, 파란색 보드인지에 따라서 값을 조정해줬습니다.
dropBlock(GREEN, yy1, xx1, yy2, xx2, t == 3 ? 1 : t);
dropBlock(BLUE, xx1, yy1, xx2, yy2, t == 3 ? 2 : 1);초록색 보드일 땐, t == 3일 땐 '|' 모양이니까 int block을 1로 해줬고
나머지 타입은 그대로 넣어줬습니다.
파란색 보드일 땐, t == 3일 땐 '--' 모양이니까 int block을 2로 해줬고
나머지 타입은 1로 넣어줬습니다.
파란색 보드는 초록색 보드를 90도 돌린 다음 옆으로 뒤집은 형태이기 때문에
'--' 모양은 '|'로 들어오고, '|'모양은 '--' 모양으로 들어옵니다.
이제 downBlock 구현부를 봅시다.
// 블럭 내리는 함수
void downBlock(int board, int row) {
for (int r = row; r >= 4; r--) {
for (int c = 0; c < 4; c++) {
if (boards[board][r][c] == 1) {
boards[board][r][c] = 0;
dropBlock(board, r, c, r, c, 1);
}
else if (boards[board][r][c] == 2) {
boards[board][r][c] = boards[board][r][c + 1] = 0;
dropBlock(board, r, c, r, c + 1, 2);
}
}
}
}밑에서부터 위로 탐색하며 블럭의 타입에 따라 블럭을 알맞게 내리면 됩니다.
보면 아시겠지만
1은 마이웨이니까 boards[board][r][c] = 0;로 그 부분을 지워주고
dropBlock(board, r, c, r, c, 1);을 호출함으로써 끝까지 내려줬지만
2는 세트니까 boards[board][r][c] = boards[board][r][c + 1] = 0;로 세트로 지워주고
dropBlock(board, r, c, r, c + 1, 2);을 호출함으로써 세트로 내려줍니다.
2를 내려줄 때 단순히 이런 로직이 통하는 이유는
2가 존재할 수 있는 경우의 수는 2200, 0220, 0022말곤 없습니다.
절대로 2002, 2020, 0202같이 떨어져 있을 수가 없습니다.
'--' 얘는 세트라서 사라지면 같이 사라지기 때문에
2200, 0220, 0022 << 이 경우의 수만 신경쓰면 됩니다.
추가적으로 설명드릴 부분이 있다면
downBlock은 인자로 받은 row행부터 차근차근 위로 올라오면서 블럭들을 내려줍니다.
row행을 받은 이유는, 만약 7번째 행이 삭제됐다고 해봅시다.
그러면 그 위에 있는 6이하의 행들은 영향을 받지만, 7밑에 있는 행들은 영향을 받지 않기 때문입니다.
여기까지 시뮬레이션 해보기
현재 상태
0220
2200
1000
2210
0122
3 0 3 투입! -> '|' 모양 맨 오른쪽에 삽입
0220
2200
1001
2211
0122
밑에서 두 번째 줄 삭제
0220
2200
1001
0000
0122
밑에서 세 번째 줄 내리기
0220
2200
0000
0001
1122
밑에서 네 번째 줄 내리기
0220
0000
0000
2201
1122
밑에서 다섯 번째 줄 내리기
0000
0000
0220
2201
1122
맨 밑줄 삭제
0000
0000
0220
2201
0000
밑에서 두 번째 줄 내리기
0000
0000
0220
0000
2201
밑에서 세 번째 줄 내리기
0000
0000
0000
0220
2201
이런 식으로 더 이상 삭제할 행이 없을 때까지 반복합니다.
4. 연한 칸 처리하기
void handleSoftCell(int board) {
int count = 0;
for (int r = 5; r >= 4; r--) {
for (int c = 0; c < COL; c++) {
if (boards[board][r][c] > 0) {
count++;
break;
}
}
if (count == 0) return;
}
for (int r = ROW - 1; r > ROW - 1 - count; r--) {
deleteRow(board, r);
}
downBlock(board, ROW - 1 - count);
}연한 칸에 블럭이 있는지 체크해서 그만큼 밑에 줄 삭제하고
downBlock을 호출해서 블럭을 내려주면 됩니다.
3. 전체 코드
#define ROW 10
#define COL 4
#define GREEN 0
#define BLUE 1
#include <bits/stdc++.h>
using namespace std;
int n, t, yy1, xx1, yy2, xx2;
int score = 0;
int boards[2][ROW][COL];
int my[3] = { 0, 0, 1 };
int mx[3] = { 0, 1, 0 };
// 블럭 떨구는 함수
void dropBlock(int board, int y1, int x1, int y2, int x2, int block) {
while (y1 < ROW && y2 < ROW && boards[board][y1][x1] == 0 && boards[board][y2][x2] == 0) {
y1++;
y2++;
}
boards[board][y1 - 1][x1] = boards[board][y2 - 1][x2] = block;
}
// 행 삭제
void deleteRow(int board, int r) {
for (int c = 0; c < COL; c++) {
boards[board][r][c] = 0;
}
}
// 블럭 내리는 함수
void downBlock(int board, int row) {
for (int r = row; r >= 4; r--) {
for (int c = 0; c < 4; c++) {
if (boards[board][r][c] == 1) {
boards[board][r][c] = 0;
dropBlock(board, r, c, r, c, 1);
}
else if (boards[board][r][c] == 2) {
boards[board][r][c] = boards[board][r][c + 1] = 0;
dropBlock(board, r, c, r, c + 1, 2);
}
}
}
}
// 더 이상 삭제할 행이 없을 때까지 행 삭제하는 함수
void deleteRowUntillAble(int board) {
while (1) {
int maxDeletedRow = -1;
// 행 삭제
for (int r = 4; r < ROW; r++) {
int isDelete = 1;
for (int c = 0; c < COL; c++) {
if (boards[board][r][c] == 0) {
isDelete = 0;
break;
}
}
if (!isDelete) continue;
deleteRow(board, r); // 행 삭제
score++; // 점수 증가
maxDeletedRow = r;
}
if (maxDeletedRow == -1) break;
downBlock(board, maxDeletedRow - 1);
}
}
// 연한 칸처리 함수
void handleSoftCell(int board) {
int count = 0;
for (int r = 5; r >= 4; r--) {
for (int c = 0; c < COL; c++) {
if (boards[board][r][c] > 0) {
count++;
break;
}
}
if (count == 0) return;
}
for (int r = ROW - 1; r > ROW - 1 - count; r--) {
deleteRow(board, r);
}
downBlock(board, ROW - 1 - count);
}
// 셀 개수
int getCellCount(int board) {
int ret = 0;
for (int i = 6; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (boards[board][i][j] > 0) ret++;
}
}
return ret;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
while (n--) {
cin >> t >> yy1 >> xx1;
yy2 = yy1 + my[t - 1];
xx2 = xx1 + mx[t - 1];
dropBlock(GREEN, yy1, xx1, yy2, xx2, t == 3 ? 1 : t);
deleteRowUntillAble(GREEN);
handleSoftCell(GREEN);
dropBlock(BLUE, xx1, yy1, xx2, yy2, t == 3 ? 2 : 1);
deleteRowUntillAble(BLUE);
handleSoftCell(BLUE);
}
cout << score << '\n' << (getCellCount(GREEN) + getCellCount(BLUE));
return 0;
}