[BOJ] Puyo Puyo - 11559

Kyeongminยท2021๋…„ 9์›” 29์ผ
0

์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ชฉ๋ก ๋ณด๊ธฐ
10/24

๐Ÿ“ƒ ๋ฌธ์ œ

[BOJ] Puyo Puyo ๐Ÿ”—๋งํฌ


โ“ ๋ฌธ์ œ ์ ‘๊ทผ

  1. ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋ฌธ์ œ๋ผ์„œ ์šฐ์„  ๊ตฌํ˜„๋ถ€ํ„ฐ ํ•˜๊ณ  ๊ทธ ์ดํ›„์— ์ตœ์ ํ™”๋ฅผ ํ•˜๊ธฐ๋กœ ์ƒ๊ฐํ–ˆ๋‹ค.
  2. ๊ตฌํ˜„ ๋กœ์ง์„ 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);
    }
}

๐Ÿง  ์ตœ์ ํ™” ํ’€์ด

  1. ์ž…๋ ฅ์„ ๋ฌธ์ž ๊ทธ๋Œ€๋กœ ์ž…๋ ฅ ๋ฐ›์•„ ๋ฌธ์ž โ†’ ์ •์ˆ˜ ์น˜ํ™˜ ๋ถ€๋ถ„์„ ์ œ๊ฑฐํ–ˆ๋‹ค.
  2. DFS๋ฅผ ์žฌ๊ท€๋กœ ๊ตฌํ˜„ํ•˜์—ฌ stack ์‚ฌ์šฉ ๋ถ€๋ถ„์„ ์ œ๊ฑฐํ–ˆ๋‹ค.
  3. 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);
    }
}
profile
๊ฐœ๋ฐœ์ž๊ฐ€ ๋˜๊ณ  ์‹ถ์€ ๊ณต์žฅ์žฅ์ด๐Ÿ› 

0๊ฐœ์˜ ๋Œ“๊ธ€