풀이일시 : 2021-02-13
문제 :
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.
이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다.
블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계를 만나기 전까지 계속해서 이동한다. 예를 들어, 크기가 1×1인 블록을 (1, 1)에 놓으면, 보드의 상태는 <그림 3>과 같이 변한다.
여기서 크기가 1×2인 블록을 (3, 0)과 (3, 1)에 놓으면 <그림 4>와 같이 보드의 상태가 변한다.
다시 이 상태에서 크기가 2×1인 블록을 (2, 2), (3, 2)와 (2, 3), (3, 3)에 놓으면 <그림 5>와 같이 변한다.
초록색 보드의 4번 행은 모든 칸이 타일로 가득 차있다. 이렇게 초록색 보드에서 어떤 행이 타일로 가득 차 있다면, 그 행의 타일은 모두 사라진다. 사라진 이후에는 초록색 보드에서 사라진 행의 위에 있는 블록이 사라진 행의 수만큼 아래로 이동한다. 파란색의 경우는 열이 타일로 가득 차 있으면, 그 열의 타일이 모두 사라지며, 사라진 이후에는 파란색 보드에서 사라진 열의 왼쪽에 있는 블록이 사라진 열의 수만큼 오른쪽으로 이동한다. 이렇게 한 행이나 열이 타일로 가득 차서 사라지면 1점을 획득한다. 점수는 사라진 행 또는 열의 수와 같다. 만약, 두 개의 행이 사라지면 2점을 획득하게 되고, 한 행과 한 열이 사라져도 2점을 획득하게 된다. 위의 보드는 아래와 같이 변하고, 1점을 얻는다.
여기서 크기가 2×1인 블록을 (1, 3), (2, 3)에 놓으면 보드는 <그림 7>과 같이 변한다.
초록색 보드의 0, 1번 행과 파란색 보드의 0, 1번 열은 그림에는 연한색으로 표현되어 있는 특별한 칸이다. 초록색 보드의 0, 1번 행에 블록이 있으면, 블록이 있는 행의 수만큼 아래 행에 있는 타일이 사라지고, 초록색 보드의 모든 블록이 사라진 행의 수만큼 아래로 이동하고, 파란색 보드의 0, 1번 열에 블록이 있으면, 블록이 있는 열의 수만큼 오른쪽 열에 있는 타일이 사라지고, 파란색 보드의 모든 블록이 사라진 열의 수만큼 이동하게 된다. 위의 그림은 파란색 보드의 1번 열에 블록이 있기 때문에, 5번 열에 있는 블록이 모두 사라지고, 파란색 보드의 모든 블록이 오른쪽으로 한 칸 이동하게 된다. 따라서, 보드는 <그림 8>과 같이 변하게 된다.
위의 보드에서 1×2인 블록을 (0, 0), (0, 1)에 놓으면 <그림 9>와 같다.
여기서 크기가 2×1인 블록을 (2, 0), (3, 0)에 놓으면 <그림 10>과 같이 변한다. 파란색 보드는 1번 열에 블록이 생겨서 오른쪽으로 한 칸씩 이동한 상태이다.
크기가 2×1인 블록을 (1, 2), (2, 2)에 놓으면, <그림 11>과 같이 변한다.
파란색 보드는 1번 열에 블록이 있기 때문에, 5번 열의 타일이 사라지고 모든 블록이 오른쪽으로 한 칸씩 이동하게 된다. 초록색 보드는 4번 행의 모든 칸에 타일이 있기 때문에, 1점을 얻으면서, 4번 행의 모든 타일이 사라진다.
<그림 12>는 <그림 11>의 상태에서 파란색 보드는 모든 블록이 오른쪽으로 한 칸 이동했고, 초록색 보드의 4번 행이 모두 사라진 상태이다. 이제, 초록색 보드에서 사라진 행의 위에 있는 블록이 아래로 한 칸씩 내려와야 한다. 이동한 후의 상태는 <그림 13>과 같다.
행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.
블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.
입력 :
첫째 줄에 블록을 놓은 횟수 N(1 ≤ N ≤ 10,000)이 주어진다.
둘째 줄부터 N개의 줄에 블록을 놓은 정보가 한 줄에 하나씩 순서대로 주어지며, t x y와 같은 형태이다.
- t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우
- t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우
- t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우
블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.
출력 :
첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.
둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.
풀이 :
특별히 쓰인 알고리즘은 없는 구현 문제이다.
문제에 쓰인 조건들을 충실히 구현해주면 풀 수 있는 문제이다.
다만 구현중에 실수할 수 있는 포인트들은 있다.
1) 블럭을 넣을 때 뒤에서부터 확인하며 채워넣으면 안된다.
위 사진으로 설명할 수 있다. X 부분은 뒤에서부터 확인하며 자리가 있자 채워넣은 상황이다. 이러면 문제의 조건과 맞지 않다. 테트리스를 생각해보면 된다.
O 표시와 같이 위에 차곡차곡 쌓여야 된다. 이를 위해서는 앞에서부터 채우며 갱신해 나가면 된다. (index사용)
2) 행,열을 지우며 점수를 올릴 때 다시 그 행,열로 돌아와야 한다.
다음과 같은 경우에는 9열을 지우고 점수를+1 시킨다. 그리고 8열의 점수를 9열로 옮기면 된다. 이상이 없다.
하지만 이와 같은 경우에는 9열을 지우고 8열을 9열로 옮겼는데도 8열도 (1,1,1,1) 이여서 또 9열에 지워야 할게 생겼다. 따라서 지우고 난 이후에는 다시 그 자리부터 탐색을 시작해 줘야 할 것이다.
소스코드의 주석을 보며 이해할 수 있다.
#include <iostream>
#include <string>
using namespace std;
int map[10][10] = { 0, };
int N, t, x, y;
int result;
void input() {
if (t == 1) { //블럭하나
for (int i = 4; i <= 9; i++) { //파란색에 넣어준다.
if (i == 9) { //9로 가면 i+1이 존재하지 않기때문에 9에 넣어준다.
map[x][i] = 1;
break;
}
if (map[x][i + 1] == 1) { //그다음게 막혀있다면
map[x][i] = 1; //i 칸에 1을 넣고 break 한다.
break;
//만약 막혀있지 않다면 i가 break되지않고 계속 증가할것
}
}
for (int i = 4; i <= 9; i++) { //초록색에 넣어준다.
if (i == 9) {
map[i][y] = 1;
break;
}
if (map[i + 1][y] == 1) {
map[i][y] = 1;
break;
}
}
}
else if (t == 2) { // 가로로 두칸짜리가 들어갈때
int idx = 10; // 하나도 없을때는 map[x][i]==1에 걸리지 않기때문에 조치가 필요하다.
for (int i = 4; i <= 9; i++) { //파란색에 들어갈 때
if (map[x][i] == 1){ //그칸이 막혀있다면 이 전칸 두개에 넣어줘야됨
idx = i;
break;
}
}
map[x][idx - 1] = 1; //걸리든 안걸리든 한번에 여기서 넣어준다.
map[x][idx - 2] = 1;
idx = 10;
for (int i = 4; i <= 9; i++) { //초록색일때 2번은 가로로 들어갈것이다.
if (map[i][y] == 1 || map[i][y + 1] == 1) {
idx = i;
break;
}
}
map[idx - 1][y] = 1;
map[idx - 1][y + 1] = 1;
}
else if (t == 3) {
int idx = 10;
for (int i = 4; i <= 9; i++) { //파란색일때 3번은 가로로 들어간다.
if (map[x][i] == 1 || map[x + 1][i] == 1) { //둘중하나 막혀있다면 못들어가
idx = i;
break;
}
}
map[x][idx - 1] = 1;
map[x + 1][idx - 1] = 1;
idx = 10;
for (int i = 4; i <= 9; i++) { //초록색
if (map[i][y] == 1) {
idx = i;
break;
}
}
map[idx - 1][y] = 1;
map[idx - 2][y] = 1;
}
}
void cntplus() {
for (int i = 9; i >= 6; i--) { //파란색일때 열을 지워가며 점수올린다.
int flag = 0; //열을 돌때마다 플래그를 세운다.
for (int j = 0; j < 4; j++) {
if (map[j][i] == 0) {
flag = 1; //하나라도 0이면 flag가 1이 될것
break;
}
}
if (flag == 0) { //해당 i 열이 1로 꽉 찬경우
result++; //점수를 한점 올린다.
for (int k = i; k >= 4; k--) { //이동시키기
for (int l = 0; l < 4; l++) {
map[l][k] = map[l][k - 1]; //한칸씩 뒤로 민다.
}
}
i++; //다 1이여서 한칸씩 미룬 경우에는 다시 i부터 확인해줘야될 것이다.
}
}
//초록색
for (int i = 9; i >= 6; i--) {
int flag = 0;
for (int j = 0; j < 4; j++) {
if (map[i][j] == 0) {
flag = 1;
break;
}
}
if (flag == false) {
result++;
for (int k = i; k >= 4; k--) {
for (int l = 0; l < 4; l++) {
map[k][l] = map[k - 1][l];
}
}
i++;
}
}
}
void pastel() { //연한 경우
int checkingcount = 0;
for (int i = 4; i <= 5; i++) {
for (int j = 0; j < 4; j++) {
if (map[j][i] == 1) {
checkingcount++; //몇칸을 미룰지 결정하는 count이다
break;
}
}
}
if (checkingcount != 0) {
for (int i = 9; i >= 4; i--) {
for (int j = 0; j < 4; j++) {
map[j][i] = map[j][i - checkingcount];
}
}
}
for (int i = 4; i <= 5; i++) { //처음 input을 줄때 3열에 input이 들어갈 수도 있었다.
for (int j = 0; j < 4; j++) { //따라서 여기서 4,5 전체를 비워준다.
map[j][i] = 0;
}
}
//연한 초록색
checkingcount = 0;
for (int i = 4; i <= 5; i++) {
for (int j = 0; j < 4; j++) {
if (map[i][j] == 1) {
checkingcount++;
break;
}
}
}
if (checkingcount != 0) {
for (int i = 9; i >= 4; i--) {
for (int j = 0; j < 4; j++) {
map[i][j] = map[i - checkingcount][j];
}
}
}
for (int i = 4; i <= 5; i++) {
for (int j = 0; j < 4; j++) {
map[i][j] = 0;
}
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> t >> x >> y; //x,y에 넣고 바로 실행하니 어디있는지 찾는과정이 필요없다.
input(); //블럭을 파란색, 초록색으로 집어넣기
cntplus(); //꽉찬 행,열을 지우고 점수를 획득한다.
pastel(); //연한 곳 처리
}
cout << result << endl;
int hap = 0;
for (int i = 9; i >= 4; i--) {
for (int j = 0; j <= 3; j++) {
if (map[j][i] == 1)
hap += 1;
if (map[i][j] == 1)
hap += 1;
}
}
cout << hap;
return 0;
}'알고리즘 문제풀이 > 삼성역량테스트' 카테고리의 다른 글
| [삼성역량테스트] 17825 주사위윷놀이 (0) | 2021.03.14 |
|---|---|
| [삼성역량테스트] 2143 두 배열의 합 (0) | 2021.02.22 |
| [삼성역량테스트] 19236 청소년상어 (0) | 2021.02.12 |
| [삼성역량테스트] 19238 스타트택시 (0) | 2021.01.25 |
| [삼성역량테스트] 20055 컨베이어 벨트 위의 로봇 (0) | 2021.01.18 |
댓글