11559_puyopuyo

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

11559번: Puyo Puyo

 

접근 

- dfs를 통해 인접한 같은 컬러의 뿌요를 탐색해 나간다

- 탐색으로 인해 추가된 뿌요의 갯수가 4개 이상이라면 터뜨린다

- 터뜨린 빈 공간에 나머지 뿌요를 하단으로 밀착시킨다

- 시뮬레이션 + dfs 문제

 

*주의

- 연쇄의 수를 세는 것이므로 가능한 모든 뿌요를 터뜨린 다임 카운트를 1 증가 시킨다

#include <iostream>
#include <vector>

using namespace std;
struct pos{int y, x;};
vector<pos> brokens;
typedef vector<vector<int>> table;
int dy[4] {-1, 1, 0, 0};
int dx[4] {0, 0, -1, 1};
char map[12][6];
void search(char color, int y, int x, table &visited){
    
    brokens.push_back({y, x});
    
    for(int i = 0 ; i < 4 ; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= 12 || nx < 0 || nx >= 6) continue;
        if(visited[ny][nx] > 0 || map[ny][nx] != color) continue;
        visited[ny][nx] += 1;
        search(color, ny, nx, visited);
    }
}

int main(int argc, const char * argv[]) {
    for(int y = 0 ; y < 12; y++){
        for(int x = 0 ; x < 6 ; x++){
            cin>>map[y][x];
        }
    }
    int cnt = 0;
    bool flag = true;
    while(flag){
        flag = false;
        //simulation
        for(int y = 0 ; y < 12; y++){
            for(int x = 0 ; x < 6 ; x++){
                if(map[y][x] == '.') continue;
                table visited = table(12, vector<int>(6, 0));
                visited[y][x] = true;
                brokens.clear();
                search(map[y][x], y, x, visited);
                if(brokens.size()<4) continue;
                
                for(pos b : brokens){
                    map[b.y][b.x] = '.';
                }
                flag = true;
            }
        }
        if(!flag) break;
        cnt += 1;
        for(int y = 11 ; y >= 0; y--){
            for(int x = 5 ; x >= 0 ; x--){
                if(map[y][x] == '.') continue;
                int ny = y;
                while(map[ny+1][x] == '.'){
                    swap(map[ny][x], map[ny+1][x]);
                    ny+=1;
                }
            }
        }

        
    }
    cout<<cnt<<endl;
    
    
    
   
    
    return 0;
}