티스토리 뷰
1. 문제 링크
19235번: 모노미노도미노
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행,
www.acmicpc.net
2. 문제 개요
가로 칸, 세로 칸이 있다. 블록이 생성되고 블록을 이동시킨다. 4줄이 가득 차면 지우고 블록을 다시 내리고... 등등 색깔이 연한 칸에 블록이 있으면 밑에서부터 지우고.. 등등의 작업을 한다. 점수와 남은 블록의 개수를 출력하는 프로그램을 만들자.
3. 문제 힌트
하나 하나의 동작을 모듈화 시키자.
특별한 알고리즘은 필요 없다.
침착하게 블록들을 어떻게 표현할 수 있을까?
표현한 블록들을 어떻게 움직일 수 있을까? 를 잘 생각해보자.
4. 문제 풀이
이런 문제에서 가장 중요한 것은 모듈화라고 생각한다. 하나의 함수에는 하나의 동작을 나타내는 코드를 만들자.
그렇지 않고 주루루루룩 할 경우, 실력이 좋다면 AC 하겠지만 그렇지 않으면 어디서 틀렸는지도 모르고 시험장에서 멘탈이 아주 종이 쪼가리가 되어버릴 것이다. 그래서 어떻게 블록을 표현할 것인지, 하나하나 동작을 정의한 뒤 그냥 문제에 적힌 대로 호출만 해주면 된다.
우선, 맵이 왼쪽-> 오른쪽 방향과 위-> 아래 방향 두 가지가 있다.
첫 번째로 했던 고민은 이렇게 방향이 두 가지가 있는데 이러면 위-> 아래 왼쪽-> 오른쪽의 함수를 2개 만들어야 한다는 점이다. 어떻게 회전 변환(?)을 주어서 한 개로 처리할 수는 없을까?라고 생각해봤지만 pass
본론으로 돌아와서,
필요한 함수(모듈)는 다음과 같다.
1. 블록 생성.
2. 블록 옮기기 (2가지 left->right, up -> down)
2-1 블록 1개 끝까지 옮기기
3. 블록 한 줄 가득 찼는지 검사 (2가지)
4. 블록 한 줄 지우기 (2가지)
5. 연한 색 부분 블록이 존재하는지 검사(2가지)
위의 함수들만 짜 놓으면 이 문제를 구현할 수 있다.
대부분의 사람들이 블록을 어떻게 옮길지, 블록을 표현하는 방법에 있어서 많이 틀렸을 것 같다.
우선 맵은
가로 배열(4 x 10), 세로 배열(10 x 4) 2가지로 나타내었다.
블록은
위의 그림과 같이 있고, 맵에서 블록의 존재를 위해 코드에서는 1x1은 1, 1x2는 2, 2x1은 3으로 나타낼 것이다.
여기서 중요한 점은, 우리에게 익숙한 세로모양 배열에서, 1x1블록이나 2x1이나 똑같다는 것이다.
2x1을 3으로 나타내기보다는 1x1의 2개로 나타낼 수 있다는 것이다. 어차피 블록은 1줄, 가로 모양으로 삭제 되기 때문에,
쪼개진 모양은 1x1과 같기 때문이다.
이와 같은 개념으로 가로모양 맵에서는 1x2가 1x1 2개로 나타내어질 수 있다.
따라서 세로 모양 맵에서는 1과 2가 있을 것이고, 가로 모양 맵에서는 1과 3이 존재할 것이다.
이점을 유념해서 블록을 놓는 함수를 정의하자.
이제 블록을 옮겨야 한다.
세로모양 맵을 기준으로 설명하면, 블록을 놓는 공간 4x4 행렬의 밑에서부터 탐색해서 맨 밑으로 옮긴다.
블록을 옮기는 함수는 해당 좌표의 블록을 밑으로 한 칸 움직이는 함수를 정의했고, 한 칸 움직이는 함수를 재귀적으로 계속 호출하여 맨 밑까지 옮겨주는 방식으로 구현을 했다.
이렇게 1칸의 블록을 맨 밑으로 옮겨주는 방식으로 구현을 하고, 위에서 말했던 4x4행렬의 밑에서부터 탐색해서 이 블록 한개를 맨밑으로 옮기는 함수를 호출하여 해당 범위의 블록을 모두 밑으로 보낸다. 이와 같이 한 블록에 대해 이동하는 함수를 구현해놓으면 단순히 반복문을 더해준다면 해당 범위의 블록을 모두 밑으로 내리는 함수를 간단히 구현할 수 있다.
이렇게 밑으로 다 보냈으면 이제 가득 찬 줄을 찾아야 한다.
가득찬 줄은 단순히 해당 행 번호를 입력으로 받아 해당 행에 빈칸이 존재하는지 찾으면 된다.
블록을 지우는 것 또한 위에 정의한 한 줄이 가득 찬 모듈에 의해 가득찼다고 반환하면 그 행에 대해서 모두 블록을 삭제해주기만 하면된다. 행번호를 입력으로 받아 삭제하는 함수를 정의하자.
이 모듈을 구현해놓으면, 이 맵의 범위에 가득찬 공간이 없을 때까지 반복하고, 블록을 내리고 삭제하고 내리고 삭제하고만 반복으로 구현하면 문제없이 작동한다.
또, 색깔이 연한 부분에 블록이 있는지 탐색하고(이거는 가득 찬 거랑은 다르기 때문에 새로 구현) 있다면 이전에 구현했던 삭제하는 함수를 사용해서 그 개수만큼 가장 밑에서 지우고, 기존에 구현했던 블록을 내리는 함수를 재활용해서 내리기만 하면 이 부분도 해결 가능.
이런 식으로 필요한 동작을 구현하되 하나의 함수에서는 하나의 동작만 하도록 구현하는 것이 핵심이다.!! 이 부분은 말로 해도 습관화하기 어려우니, 여러 번 해보는 걸 추천한다. (실제 알고리즘 말고 개발할 때도 이런 습관이 중요합니다.)
가로 모양 맵에 대해서는 이와 같은 논리로 함수를 한 개씩 더 작성하여 문제를 해결해주자.
또, 이렇게 하다 보면 블록을 밀 때 예외 케이스를 하나 만나게 되는데,
가로 맵 기준으로,
2x1블록을 3번이라고 하고, 빨간색 화살표 방향으로 탐색을 이어나갈 때, 3번을 만나면 2x1블록을 오른쪽으로 한 칸 이동한다. 하지만 초록색 1번 같은 경우는 오른쪽에 1이 있기 때문에 stop.
하지만 초록색 2번을 만나는 경우에 3번 블록은 서로 끊어질 수 없기 때문에 움직이면 안 된다. 그런데 움직여버리게 되므로.. 왜냐하면 오른쪽에 아무 블록도 없기 때문이다. 따라서 진행하는 방향의 첫 번째 블록만 3으로 해두고, 그 외는 블록이 존재함을 나타내기만 하면 되니 -3과 같은 값으로 해두어서 해결할 수 있다.
(이해가 잘 안될 수도 있으나, 이 예외 케이스가 정답률을 꽤나 낮춘데 영향을 주지 않았나 싶습니다.)
5. 코드
#include <cstdio>
using namespace std;
int row[4][10], col[10][4]; //map
int n, ans, score;
void put_block(int y, int x , int type) //y : row, x : col
{
if (type == 1){
// 1*1 block
row[y][x] = col[y][x] = 1;
}
else if (type == 2) {
// 1*2 block
row[y][x] = row[y][x + 1] = 1;
col[y][x] = 2; col[y][x + 1] = -2;
}
else{
// 2*1block
row[y][x] = 3; row[y + 1][x] = -3;
col[y][x] = col[y + 1][x] = 1;
}
}
void move_right(int y, int x)
{
if (row[y][x] == 1){
if (x < 9)
if (row[y][x + 1] == 0) {
row[y][x] = 0;
row[y][x + 1] = 1;
move_right(y, x + 1);
}
}
else if (row[y][x] == 3){
if (x < 9) {
if (row[y][x + 1] == 0 && row[y + 1][x + 1] == 0)
{
row[y][x] = row[y + 1][x] = 0;
row[y][x + 1] = 3; row[y + 1][x + 1] = -3;
move_right(y, x + 1);
}
}
}
return;
}
void push_right(int start, int end)
{
//[start, end]
for (int j = end; j >= start; --j)
for (int i = 0; i < 4; ++i)
if (row[i][j] != 0)
move_right(i, j);
return;
}
void move_down(int y, int x)
{
if (col[y][x] == 1){
if (y < 9)
if (col[y + 1][x] == 0){
col[y][x] = 0;
col[y + 1][x] = 1;
move_down(y + 1, x);
}
}
else if(col[y][x] == 2){
if (y < 9)
if (col[y + 1][x] == 0 && col[y + 1][x + 1] == 0){
col[y][x] = col[y][x + 1] = 0;
col[y + 1][x] = 2; col[y + 1][x + 1] = -2;
move_down(y + 1, x);
}
}
return;
}
void push_down(int start, int end)
{
//[start, end]
for (int i = end; i >= start; --i)
for (int j = 0; j < 4; ++j)
if (col[i][j] != 0)
move_down(i, j);
return;
}
bool isfull_row(int y) {
//if a row is full, then return true.
for (int j = 0; j < 4; ++j)
if (col[y][j] == 0)
return false;
return true;
}
bool isfull_col(int x) {
for (int i = 0; i < 4; ++i)
if (row[i][x] == 0)
return false;
return true;
}
void erase_row(int y)
{
for (int j = 0; j < 4; ++j)
col[y][j] = 0;
return;
}
void erase_col(int x)
{
for (int i = 0; i < 4; ++i)
row[i][x] = 0;
return;
}
bool warning_erea_row(int y)
{
for (int j = 0; j < 4; ++j)
if (col[y][j] != 0)
return true;
return false;
}
bool warning_erea_col(int x)
{
for (int i = 0; i < 4; ++i)
if (row[i][x] != 0)
return true;
return false;
}
int main()
{
scanf("%d", &n);
while (n--)
{
//t, row(x), col(y) -> t, row(y), col(x)
int t, x, y;
scanf("%d %d %d", &t, &y, &x);
//construct block
//push initial block
put_block(y, x, t);
push_right(0, 3);
push_down(0, 3);
//check block of lines
bool flag = true;
//row first
while (flag){
flag = false;
for (int j = 6; j <= 9; ++j) {
if (isfull_col(j)) {
++score;
erase_col(j);
flag = true;
}
}
if (flag)
push_right(4, 8);
}
int cnt = 9;
if (warning_erea_col(5))
erase_col(cnt--);
if (warning_erea_col(4))
erase_col(cnt--);
if (cnt != 9)
push_right(4, 8);
flag = true;
//col
while (flag) {
flag = false;
for (int i = 6; i <= 9; ++i) {
if (isfull_row(i)) {
++score;
erase_row(i);
flag = true;
}
}
if (flag)
push_down(4, 8);
}
cnt = 9;
if (warning_erea_row(5))
erase_row(cnt--);
if (warning_erea_row(4))
erase_row(cnt--);
if (cnt != 9)
push_down(4, 8);
}
for (int i = 6; i <= 9; ++i)
for (int j = 0; j < 4; ++j)
{
if (col[i][j] != 0)
++ans;
if (row[j][i] != 0)
++ans;
}
printf("%d\n%d",score, ans);
return 0;
}
6. 실행 결과
'알고리즘 > 삼성 SW테스트' 카테고리의 다른 글
| boj, 백준) 20055. 컨베이어 벨트 위의 로봇 ( C / C++ ) (0) | 2020.10.25 |
|---|---|
| boj, 백준) 20061. 모노미노도미노2 ( C / C++ ) (0) | 2020.10.23 |
| boj, 백준) 19238. 스타트택시 ( C / C++ ) (0) | 2020.10.11 |
| boj, 백준) 19237. 어른상어 ( C / C++) (13) | 2020.07.31 |
| boj, 백준) 19236. 청소년 상어 ( C / C++) (2) | 2020.07.03 |