[BOJ] Puyo Puyo - 11559

📃 문제

[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);
    }
}