๐ ๋ฌธ์
โ ๋ฌธ์ ์ ๊ทผ
- ์๋ฎฌ๋ ์ด์
๋ฌธ์ ๋ผ์ ์ฐ์ ๊ตฌํ๋ถํฐ ํ๊ณ ๊ทธ ์ดํ์ ์ต์ ํ๋ฅผ ํ๊ธฐ๋ก ์๊ฐํ๋ค.
- ๊ตฌํ ๋ก์ง์ 3๋จ๊ณ๋ก ๋๋์๋ค. (์ฐ์ ๋ธ๋ญ ํ์ธ โ ์ฐ์ ๋ธ๋ญ ์ ๊ฑฐ โ ๋จ์ด์ง๋ ๋ธ๋ญ ์ด๋)
- ์ฐ์ ๋ธ๋ญ ํ์ธ
checkBlock()
: ์ฃผ์ด์ง๋ Field(6x12)๊ฐ ์์ DFS๋ฅผ ์ด์ฉํ์ฌ ์ฐ๊ฒฐ๋ ๋ธ๋ญ์ ํ์ธํ๋ค.
- ์ฐ์ ๋ธ๋ญ ์ ๊ฑฐ
removeBlock()
: ์ฐ๊ฒฐ๋ ๋ธ๋ญ๋ค์ ์ขํ๋ฅผ stack์ผ๋ก ๋ฐ์์ ๋น ๊ณต๊ฐ์ผ๋ก ์ด๊ธฐํํ๋ค.
- ๋จ์ด์ง๋ ๋ธ๋ญ ์ด๋
moveBlock()
: ์์ ํ๋ํ๋ Shift ํ๋ ๊ฑด ๋๋ฌด ๋นํจ์จ์ ์ด๋ผ๊ณ ๋๊ปด์ ธ์..
๊ฐ ์ธ๋ก์ถ์ ๋ํด ๋น ๊ณต๊ฐ์ด ์๋ ๋ธ๋ญ์ ์๋ก์ด ๋ฐฐ์ด์ ๋ฃ๊ณ , ์ด๋ฅผ Field์ ๊ฐ ์ธ๋ก์ถ์ ๋์
์์ผฐ๋ค.
์ด ๋ถ๋ถ์ ๊ตฌํํ๊ธฐ ์ฝ๊ฒํ๋ ค๊ณ ๊ฐ๋ก/์ธ๋ก๋ฅผ ๋ฐ์ ์์ผ ์
๋ ฅ ๋ฐ์๋ค.
๐ง ํ์ด
#include <iostream>
#include <cstring>
#include <stack>
#include <map>
#include <utility>
using namespace std;
int board[7][13] = {0,};
int visit[7][13] = {0,};
const int mapX = 6;
const int mapY = 12;
const int VISITED = 1;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
map<char, int> colorToNum = {{'.',0}, {'R',1}, {'G',2}, {'B',3}, {'P',4}, {'Y',5},};
stack<pair<int, int>> checkBlock(int x, int y);
bool isSafe(int x, int y);
void removeBlock(stack<pair<int,int>> *checkedBlock);
void moveBlock();
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);
cin.tie(0);
char block;
for(int i=mapY-1; i>=0; i--){
for(int j=0; j<mapX; j++){
cin >> block;
board[j][i] = colorToNum[block];
}
}
int chain = -1;
bool isChain;
do{
isChain = false;
chain++;
memset(visit, 0, sizeof(visit));
for(int i=0; i<mapX; i++){
for(int j=0; j<mapY; j++){
if(board[i][j] && !visit[i][j]){
stack<pair<int,int>> checkedBlock = checkBlock(i, j);
if(checkedBlock.size() >= 4){
isChain = true;
removeBlock(&checkedBlock);
}
}
}
}
moveBlock();
}while(isChain);
cout << chain << endl;
return 0;
}
stack<pair<int, int>> checkBlock(int x, int y){
stack<pair<int, int>> checkedBlock;
checkedBlock.push(make_pair(x,y));
stack<pair<int, int>> s;
s.push(make_pair(x,y));
visit[x][y] = VISITED;
while(!s.empty()){
int mx = s.top().first;
int my = s.top().second;
int mColor = board[mx][my];
s.pop();
for(int i=0; i<4; i++){
int nx = mx + dx[i];
int ny = my + dy[i];
if(!isSafe(nx,ny) || visit[nx][ny] || board[nx][ny]!=mColor) continue;
visit[nx][ny] = VISITED;
s.push(make_pair(nx,ny));
checkedBlock.push(make_pair(nx,ny));
}
}
return checkedBlock;
}
bool isSafe(int x, int y){
return (x>=0 && x<mapX && y>=0 && y<mapY);
}
void removeBlock(stack<pair<int,int>> *checkedBlock){
stack<pair<int,int>> s = *checkedBlock;
while(!s.empty()){
int mx = s.top().first;
int my = s.top().second;
s.pop();
board[mx][my] = 0;
}
}
void moveBlock(){
for(int i=0; i<mapX; i++){
int tmp[13] = {0,};
int tmpIndex = 0;
for(int j=0; j<mapY; j++){
if(board[i][j]){
tmp[tmpIndex++] = board[i][j];
}
}
memcpy(board[i], tmp, sizeof(int) * 13);
}
}
๐ง ์ต์ ํ ํ์ด
- ์
๋ ฅ์ ๋ฌธ์ ๊ทธ๋๋ก ์
๋ ฅ ๋ฐ์ ๋ฌธ์ โ ์ ์ ์นํ ๋ถ๋ถ์ ์ ๊ฑฐํ๋ค.
DFS
๋ฅผ ์ฌ๊ท๋ก ๊ตฌํํ์ฌ stack ์ฌ์ฉ ๋ถ๋ถ์ ์ ๊ฑฐํ๋ค.
Point
Class๋ฅผ ๋ง๋ค์ด x,y ์ขํ๋ฅผ ํํํ๋ค.
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
class Point {
public:
int x,y;
Point(int x, int y) {
this->x = x;
this->y = y;
}
};
char board[7][13] = {0,};
int visit[7][13] = {0,};
const int mapX = 6;
const int mapY = 12;
const int VISITED = 1;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
vector<Point> checkedBlock;
void checkBlock(int x, int y, char block);
bool isSafe(int x, int y);
void removeBlock();
void moveBlock();
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);
cin.tie(0);
for(int i=mapY-1; i>=0; i--){
for(int j=0; j<mapX; j++){
cin >> board[j][i];
}
}
int chain = -1;
bool isChain;
do{
isChain = false;
chain++;
memset(visit, 0, sizeof(visit));
for(int i=0; i<mapX; i++){
for(int j=0; j<mapY; j++){
if(board[i][j]!='.' && !visit[i][j]){
checkedBlock = vector<Point>();
checkBlock(i, j, board[i][j]);
if(checkedBlock.size() >= 4){
isChain = true;
removeBlock();
}
}
}
}
moveBlock();
}while(isChain);
cout << chain << endl;
return 0;
}
void checkBlock(int x, int y, char block){
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(!isSafe(nx,ny) || visit[nx][ny] || board[nx][ny]!=block) continue;
visit[nx][ny] = VISITED;
checkedBlock.push_back(Point(nx, ny));
checkBlock(nx, ny, block);
}
}
bool isSafe(int x, int y){
return (x>=0 && x<mapX && y>=0 && y<mapY);
}
void removeBlock(){
for(Point block : checkedBlock){
board[block.x][block.y] = '.';
}
}
void moveBlock(){
for(int i=0; i<mapX; i++){
char tmp[13] = {'.','.','.','.','.','.','.','.','.','.','.','.','.'};
int tmpIndex = 0;
for(int j=0; j<mapY; j++){
if(board[i][j] != '.'){
tmp[tmpIndex++] = board[i][j];
}
}
memcpy(board[i], tmp, sizeof(char) * 13);
}
}