모노미노도미노
문제 해석
10 x 4, 4 x 10 크기의 보드에 조건에 맞게 게임을 실행한 후, 지워진 행 또는 열의 수와 남은 블록 개수를 구하는 문제입니다.
특정 위치에 1x1,1x2,2x1 크기의 블록을 놓고 각 아래와 오른쪽으로 블록을 보드의 경계가 닿거나 다른 블록에 닿을 때까지 이동시킵니다.
행이나 열이 블록으로 가득 찬 경우 해당 줄을 지우고 남은 블록들을 떨어뜨립니다.
이때, 1x2와 같은 블록의 경우 서로 붙어있는 구조이기 때문에 어느 하나가 블록에 닿을 경우 멈춰줍니다.
블록을 모두 놓았을 때, 4~5행 또는 열에 블록이 있는 경우, 블록이 있는 행 또는 열의 개수만큼 보드 아래의 행 또는 열을 지우고 블록들을 다시 내려줍니다.
설계(20)
정말 어려웠던 구현문제였습니다.
보드가 두개로 구성되어있는데 10x4보드를 반시계방향으로 돌린 것이 4x10보드와 똑같은 것을 착안하여 좌표와 블록 상태만 잘 설정해주면 굳이 두개의 보드를 모두 고려하지 않아도 됩니다.
x,y => (y,3-x) or (y, 3- (x+1))로 변경을 해주면 보드를 반시계방향으로 돌리는 효과를 낼 수 있습니다.
위의 아이디어로 인해 하나의 보드가 잘 구동되게 설정하면 문제를 해결할 수 있게 되었습니다.
전체적 구조는 아래의 과정을 거치게 설계합니다.
- 블록 떨어뜨리기
- 타일이 가득찬 행을 찾아서 지운 후, 다른 블록들을 떨어뜨립니다. 이 과정을 가득찬 행이 없을 때까지 반복수행합니다.
- 4~5행에 블록이 있으면 그 행의 수만큼 아래를 지웁니다.
주의해야할 점은 행이 블록으로 가득찬 경우와 4~5행에 블록이 있는 경우가 동시에 발생한는 경우 행이 블록으로 가득 찬 경우가 없을 때까지 점수를 먼저 획득하고 다음 과정을 진행해야한다는 점입니다
위의 조건에 해당하는 지문을 읽지 않는 실수를 하였습니다.
먼저 블록 떨어뜨리기입니다. 저는 3가지 형태의 블록을 구분하기 위해서 1x1은 1, 1x2는 2와 3, 2x1을 4와 5로 각 블록을 표현하였습니다. 만약 2를 찾았으면 오른쪽에 3이 있다고 생각할 수 있게 되었습니다.
// 블록 떨어뜨리는 함수
void Drop(int t, int x, int y, vector<vector<int> >& arr) {
// 1 x 1
if (t == 1) {
arr[x][y] = 0;
for (int i = x; i < 10; i++) {
if (i + 1 == 10 || arr[i + 1][y]) {
arr[i][y] = 1;
break;
}
}
}
// 1 x 2
else if (t == 2) {
arr[x][y] = 0;
arr[x][y + 1] = 0;
for (int i = x; i < 10; i++) {
if (i + 1 == 10 || arr[i + 1][y] || arr[i + 1][y + 1]) {
arr[i][y] = 2;
arr[i][y + 1] = 3;
break;
}
}
}
else if (t == 3) {
arr[x][y] = 0;
arr[x + 1][y] = 0;
for (int i = x + 1; i < 10; i++) {
if (i + 1 == 10 || arr[i+1][y]) {
arr[i - 1][y] = 4;
arr[i][y] = 5;
break;
}
}
}
}
블록 떨어뜨리는 부분을 Drop함수로 정의하였습니다.
1x2블록의 경우 두 블록 모두 고려해서 먼저 다른 블록에 닿는 위치에 블록을 놓았습니다.
블록을 떨으뜨리는 초기 위치를 0으로 초기화한 이유는 추후에 2번에서도 Drop을 사용하는데 원래 있는 위치 정보가 남아있으면 안되기 때문입니다.
두번째로 타일이 가득찬 행이 있는지 판별하고 있으면 해당 행을 모두 지워줍니다. 이후 모든 블록을 떨어뜨립니다. 이 두가지 과정을 가득찬 행이 나오지 않을 때까지 반복해줍니다.
while (1) {
bool flag = false;
for (int i = 4; i < 10; i++) {
int cnt = 0;
for (int j = 0; j < 4; j++) {
if (arr[i][j]) cnt++;
}
if (cnt==4) {
flag = true;
ans++;
for (int j = 0; j < 4; j++) {
if (arr[i][j] == 5) {
arr[i - 1][j] = 1;
}
else if (arr[i][j] == 4) {
arr[i + 1][j] = 1;
}
arr[i][j] = 0;
}
}
}
if (!flag) break;
Find_block(arr);
}
flag로 행이 지워졌는지 체크해줍니다. arr[i][j]가 5인 경우와 4인 경우, 나머지 연결된 블록의 구조가 깨지기 때문에 1x1블록으로 변경을 해주는 과정이 필요합니다.
//떨어뜨릴 수 있는 블록 찾기
void Find_block(vector<vector<int> >& arr) {
for (int i = 9; i >= 4; i--) {
for (int j = 0; j < 4; j++) {
if (arr[i][j]==0) continue;
if (arr[i][j] == 1) {
Drop(1, i, j, arr);
}
else if (arr[i][j] == 2) {
Drop(2, i, j, arr);
}
else if (arr[i][j] == 5) {
Drop(3, i - 1, j, arr);
}
}
}
}
지워진 행이 있으므로 나머지 위의 블록들을 떨어뜨려줘야합니다. 그 과정을 Find_block 함수 정의하였습니다.
4~5행에도 우선 블록이 있을 수 있으므로 범위를 보드 경계 전부터 4행까지 모두 찾아줍니다.
// 4~5행에 블록 있는 경우, 해당 행의 수만큼 아래 행 지우기
int cnt = 0;
for (int i = 4; i <= 5; i++) {
for (int j = 0; j < 4; j++) {
if (arr[i][j]) {
cnt++;
break;
}
}
}
if (cnt) {
for (int i = 9 - cnt; i >= 4; i--) {
for (int j = 0; j < 4; j++) {
arr[i + cnt][j] = arr[i][j];
arr[i][j] = 0;
}
}
// 2 x 1 블록 아래칸 잘린경우 블록 1 x 1로 변경
for (int j = 0; j < 4; j++) {
if (arr[9][j] == 4) {
arr[9][j] = 1;
}
else if (arr[6][j] == 5) {
arr[6][j] = 1;
}
}
}
마지막 과정인 4~5행에 블록이 있는 경우 처리과정입니다.
모든 것을 다 처리하고도 4~5행에 블록이 남아있는 경우, 그 행의 수만큼 보드 아래 행들을 지워줍니다.
arr[9][i]가 4인 경우와 arr[6][j]가 5인 경우를 따로 체크했는데 그 이유는 2x1블록 구조가 깨지는 경우를 고려하기 위함입니다. 각 블록구조가 깨지면 1x1블록으로 변경해주어야합니다.
구현(60)
코드
#include <iostream>
#include <vector>
using namespace std;
int N;
int ans;
int total_ans;
// 블록 떨어뜨리는 함수
void Drop(int t, int x, int y, vector<vector<int> >& arr) {
// 1 x 1
if (t == 1) {
arr[x][y] = 0;
for (int i = x; i < 10; i++) {
if (i + 1 == 10 || arr[i + 1][y]) {
arr[i][y] = 1;
break;
}
}
}
// 1 x 2
else if (t == 2) {
arr[x][y] = 0;
arr[x][y + 1] = 0;
for (int i = x; i < 10; i++) {
if (i + 1 == 10 || arr[i + 1][y] || arr[i + 1][y + 1]) {
arr[i][y] = 2;
arr[i][y + 1] = 3;
break;
}
}
}
else if (t == 3) {
arr[x][y] = 0;
arr[x + 1][y] = 0;
for (int i = x + 1; i < 10; i++) {
if (i + 1 == 10 || arr[i+1][y]) {
arr[i - 1][y] = 4;
arr[i][y] = 5;
break;
}
}
}
}
//떨어뜨릴 수 있는 블록 찾기
void Find_block(vector<vector<int> >& arr) {
for (int i = 9; i >= 4; i--) {
for (int j = 0; j < 4; j++) {
if (arr[i][j]==0) continue;
if (arr[i][j] == 1) {
Drop(1, i, j, arr);
}
else if (arr[i][j] == 2) {
Drop(2, i, j, arr);
}
else if (arr[i][j] == 5) {
Drop(3, i - 1, j, arr);
}
}
}
}
void Simulate(int t, int x, int y, vector<vector<int> >& arr) {
// 블록 떨어뜨리기
Drop(t, x, y,arr);
while (1) {
bool flag = false;
for (int i = 4; i < 10; i++) {
int cnt = 0;
for (int j = 0; j < 4; j++) {
if (arr[i][j]) cnt++;
}
if (cnt==4) {
flag = true;
ans++;
for (int j = 0; j < 4; j++) {
if (arr[i][j] == 5) {
arr[i - 1][j] = 1;
}
else if (arr[i][j] == 4) {
arr[i + 1][j] = 1;
}
arr[i][j] = 0;
}
}
}
if (!flag) break;
Find_block(arr);
}
// 4~5행에 블록 있는 경우, 해당 행의 수만큼 아래 행 지우기
int cnt = 0;
for (int i = 4; i <= 5; i++) {
for (int j = 0; j < 4; j++) {
if (arr[i][j]) {
cnt++;
break;
}
}
}
if (cnt) {
for (int i = 9 - cnt; i >= 4; i--) {
for (int j = 0; j < 4; j++) {
arr[i + cnt][j] = arr[i][j];
arr[i][j] = 0;
}
}
// 2 x 1 블록 아래칸 잘린경우 블록 1 x 1로 변경
for (int j = 0; j < 4; j++) {
if (arr[9][j] == 4) {
arr[9][j] = 1;
}
else if (arr[6][j] == 5) {
arr[6][j] = 1;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
vector<vector<int> > arr1(10, vector<int>(4, 0));
vector<vector<int> > arr2(10, vector<int>(4, 0));
while (N--) {
int t, x, y;
cin >> t >> x >> y;
Simulate(t, x, y,arr1);
if (t == 1) {
Simulate(t, y, 3 - x, arr2);
}
else if (t == 2) {
Simulate(3, y, 3 - x, arr2);
}
else if (t == 3) {
Simulate(2, y, 3 - (x + 1), arr2);
}
}
for (int i = 6; i < 10; i++) {
for (int j = 0; j < 4; j++) {
if (arr1[i][j]) total_ans++;
if (arr2[i][j]) total_ans++;
}
}
cout << ans << "\n";
cout << total_ans << "\n";
return 0;
}
디버깅
-
Drop함수에서 각 블록의 초기위치를 0으로 초기화하지 않은 실수를 하였습니다.
-
행이 꽉찬 경우와 4~5행에 블록이 있는 경우 동시에 있는 경우를 고려하지 않았습니다. 해당 조건관련 지문이 있었는데 읽지 못하였습니다.
제출결과
4ms
마무리
삼성전자DS 상반기 기출문제로 구현하기 굉장히 어려운 문제였습니다. 실제 상반기때 풀었던 문제랑 백준에서 구현해준 문제의 난이도 차이가 있었지만, 함수를 모듈화해서 구현해주면 충분히 풀이가 가능할 것입니다.
요즘 문제를 풀면서 모듈화의 중요성에 대해서 실감을 하고 있습니다. 무조건 불필요한 반복문을 줄이기 위해서 코드를 작성했었는데, 처음부터 그렇게 문제를 풀면 디버깅지옥에 빠지기 쉽습니다.
그래서 반복문이 조금 더 있더라도 모듈화를 해서 디버깅 시간을 줄여야 할 것 같습니다.