[C++] BAEKJOON 11559 Puyo Puyo

https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

dfs 를 사용하여 문제를 해결하였습니다. 사실 dfs 를 이용한 접근보다 구현 쪽에 치중되어 있는 문제입니다.

• dfs 를 사용하여 같은 상하좌우 붙어있는 같은 색상을 찾아 해당 좌표를 v vector 에 넣어주었습니다.
• v vector 의 크기가 4 이상이면 삭제가 가능한 블록이므로 v_total vector 에 넣어주었습니다. 바로 삭제하지 않고 한 번에 모아서 삭제하는 이유는 동시에 깨지는 블록들의 경우에는 별도의 갯수로 세지 않기 때문입니다.
• v_total vector 가 비어있으면 더 이상 삭제할 블록이 없으므로 종료합니다.
• v_total 이 차있다면 해당 블록들을 제거해줍니다. 블록은 하나씩 제거하는데 아래 블록을 먼저 제거할 경우 위 쪽 블록이 영향을 받게 되므로 이를 방지하기 위해 열 기준으로 sort 해줍니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define ROW 12
#define COL 6

char board[ROW][COL];
int visited[ROW][COL];

int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0};

vector<pair<int,int>> v_total;
vector <pair<int,int>> v;

void dfs(int r, int c){
    v.push_back(make_pair(r,c));
    visited[r][c] = 1;
    char color = board[r][c];
    
    for (int i=0;i<4;i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (0<=nr && nr<ROW && 0<=nc && nc<COL){
            if (board[nr][nc] == color && !visited[nr][nc]){
                dfs(nr, nc);
            }
        }
    }
}

int compare(pair<int,int> a, pair<int,int> b){
    if (a.second < b.second) return true;
    else if (a.second == b.second) {
        if (a.first < b.first) return true;
        else return false;
    }
    return false;
}

void delete_board(void){
    sort(v_total.begin(), v_total.end(), compare);
    for (int i=0;i<v_total.size();i++){
        for (int j=v_total[i].first;j>0;j--){
            board[j][v_total[i].second] = board[j-1][v_total[i].second];
        }
        board[0][v_total[i].second] = '.';
    }
}

int main(int argc, const char * argv[]) {
    
    for (int i=0;i<ROW;i++){
        string str;
        cin >> str;
        for (int j=0;j<COL;j++){
            board[i][j] = str[j];
        }
    }
    
    int answer = 0;
    
    while (1){
        v_total.clear();
        memset(visited, 0, sizeof(visited));
        for (int i=0;i<ROW;i++){
            for (int j=0;j<COL;j++){
                if (board[i][j] !='.' && !visited[i][j]){
                    v.clear();
                    dfs(i,j);
                    if (v.size() >= 4){
                        for (int i=0;i<v.size();i++){
                            v_total.push_back(v[i]);
                        }
                    }
                }
            }
        }
        if (v_total.empty()) break;
        answer++;
        delete_board();
        
    }
    
    cout << answer << "\n";
    return 0;
}