프로그래머스 블록 게임 문제 풀이를 진행하였습니다.
문제 해석
문제를 읽으면 아래와 같은 해석이 가능합니다.
N x N크기의 맵에 블록들이 들어가 있습니다.
블록들을 총 12가지의 모양을 할 수 있으며 배치된 블록들 위로 검은 블록을 쌓을 수 있습니다.
이때 검은 블록은 선에 걸친다던가 공중에 떠 있을 수 없으며 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있습니다.
검은 블록을 떨어트려 없앨 수 있는 블록의 최댓값을 구해야합니다.
문제 풀이
주어진 12개의 블록들을 잘 살펴봐줍니다.
이 블록들 중 위에서 떨어트리는 검은 블록으로 없앨 수 있는 블록은
1번째 줄의 3번째와 4번째, 2번째 줄의 2번째와 3번째, 3번째 줄의 1번째 블록
총 5가지만 존재합니다.
그러니 주어진 맵의 블록들 중 저 5가지만 찾아서 비교 후 없앨 수 있는지 확인해주면 됩니다.
검은 블록을 계산하는 방법은 여러 가지 있지만, 저는 검은 블록을 넣을 수 있는 곳을 전부 0 -> -1로 변경해주었습니다.
그리고 모든 블록들을 찾아낸 후, 5가지가 맞는지 비교를 진행한 다음 맞다면 두개의 빈 공간에 -1이 들어가있는지 확인해줍니다.
모든 조건이 충족한다면 없앨 수 있는 블록의 수를 +1해준 후 블록을 맵에서 없앤 후 다시 블록들을 체크해줍니다.
모든 블록이 충족하지 않을 때 계산을 끝내준 후 여태까지 찾은 블록들의 수를 return해주면 됩니다.
이때 맵과 나올 수 있는 블록의 수는 다르므로 잘 생각해서 for문을 돌려주어야 합니다.
전체 코드
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;
int n;
vector<vector<int>> temp;
vector<vector<int>> blockBoard;
vector<pair<int, int>> blockPos[201];
int blockType[5][3][2] = {{{-1, 0}, {0, -1}, {0, -1}},
{{-1, 0}, {-1, 0}, {0, 1}},
{{-1, 0}, {-1, 0}, {0, -1}},
{{-1, 0}, {0, 1}, {0, 1}},
{{-1, 0}, {0, -1}, {0, 2}}};
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void findBlock(int curNumber, int x, int y) //블록 발견 및 등록
{
temp[x][y] = 0;
blockPos[curNumber].push_back(make_pair(x, y));
for(int i = 0; i < 4; i++)
{
if(x+dx[i] < 0 || x+dx[i] > n-1 || y+dy[i] < 0 || y+dy[i] > n-1)
continue;
if(temp[x+dx[i]][y+dy[i]] == curNumber)
{
findBlock(curNumber, x+dx[i], y+dy[i]);
}
}
}
void eraseBlock(int num) //블록 삭제
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(blockBoard[i][j] == num)
{
blockBoard[i][j] = 0;
}
}
}
}
void checkBlackBlock() //검은 블록 놓을 수 있는 곳을 체크
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(blockBoard[j][i] <= 0)
{
blockBoard[j][i] = -1;
}else
{
break;
}
}
}
}
int solution(vector<vector<int>> board) {
int answer = 0;
n = board.size();
blockBoard = board;
temp = blockBoard;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(temp[i][j] != 0)
{
findBlock(temp[i][j], i, j);
}
}
}
//넣을 수 있는 검은 블록을 -1로 처리
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(blockBoard[j][i] <= 0)
{
blockBoard[j][i] = -1;
}else
{
break;
}
}
}
int blockCnt = 0;
bool isBlockAble = true;
while(isBlockAble) //더 이상 블록을 제거할 수 없을 때까지 검색
{
isBlockAble = false;
for(int i = 0; i <= 200; i++)
{
if(!blockPos[i].empty())
{
for(int j = 0; j < 5; j++)
{
if(blockPos[i].empty()) //만약 블록을 지울 수 있는 경우를 찾아서 없앴을 경우 넘어감
break;
//5가지의 블록에 해당하는 블록이 있을 경우
if(blockPos[i][0].first - blockPos[i][1].first == blockType[j][0][0] &&
blockPos[i][0].second - blockPos[i][1].second == blockType[j][0][1] &&
blockPos[i][1].first - blockPos[i][2].first == blockType[j][1][0] &&
blockPos[i][1].second - blockPos[i][2].second == blockType[j][1][1] &&
blockPos[i][2].first - blockPos[i][3].first == blockType[j][2][0] &&
blockPos[i][2].second - blockPos[i][3].second == blockType[j][2][1])
{
switch(j){ //검은 블록을 놓아서 지울 수 있을 경우 제거
case 0:
if(blockBoard[blockPos[i][0].first][blockPos[i][0].second+1] == -1 &&
blockBoard[blockPos[i][0].first][blockPos[i][0].second+2] == -1)
{
answer++;
blockPos[i].clear();
eraseBlock(i);
checkBlackBlock();
isBlockAble = true;
}
break;
case 1:
if(blockBoard[blockPos[i][0].first][blockPos[i][0].second-1] == -1 &&
blockBoard[blockPos[i][1].first][blockPos[i][1].second-1] == -1)
{
answer++;
blockPos[i].clear();
eraseBlock(i);
checkBlackBlock();
isBlockAble = true;
}
break;
case 2:
if(blockBoard[blockPos[i][0].first][blockPos[i][0].second+1] == -1 &&
blockBoard[blockPos[i][1].first][blockPos[i][1].second+1] == -1)
{
answer++;
blockPos[i].clear();
eraseBlock(i);
checkBlackBlock();
isBlockAble = true;
}
break;
case 3:
if(blockBoard[blockPos[i][0].first][blockPos[i][0].second-1] == -1 &&
blockBoard[blockPos[i][0].first][blockPos[i][0].second-2] == -1)
{
answer++;
blockPos[i].clear();
eraseBlock(i);
checkBlackBlock();
isBlockAble = true;
}
break;
case 4:
if(blockBoard[blockPos[i][0].first][blockPos[i][0].second-1] == -1 &&
blockBoard[blockPos[i][0].first][blockPos[i][0].second+1] == -1)
{
answer++;
blockPos[i].clear();
eraseBlock(i);
checkBlackBlock();
isBlockAble = true;
}
break;
}
}
}
}
}
}
return answer;
}출저
https://school.programmers.co.kr/learn/courses/30/lessons/42894
게임 프로그래머 준비생