[백준]11559. Puyo Puyo

[문제]

 

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

 

[풀이]

 

 

상하좌우 중에서 같은 색깔의 뿌요가 4개 이상 존재한다면 뿌요는 터지게 된다.
뿌요들이 터지고 나서 위에 다른 뿌요들이 있다면 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

 

먼저 BFS 함수에서 상하좌우에 같은 색깔의 뿌요가 존재하는지 확인한다.

존재한다면 vector에 push 하여서 queue가 empty가 될 때까지 진행한다. 

while문을 빠져나와서 벡터의 사이즈가 4보다 크거나 같다면 뿌요가 터질 수 있는 조건을 성립하므로

뿌요가 존재하는 위치의 값을 0으로 update 해준다.

이와 같은 방식으로 모든 좌표에 대해서 확인을 한다. 

 

뿌요가 하나도 터지지 않았다면  BFS 함수가 return false  하므로 main 함수의  while문도 끝나게 된다.

return true를 했다면 뿌요가 터졌기 때문에 터진 뿌요 위에 다른 뿌요가 존재하면 아래로 내려올 수 있도록 하는 solve 함수를 호출한다.

 

solve 함수는 열을 기준으로 아래서부터 뿌요가 존재한다면 벡터에 하나씩 담아준다.

그리고 한번에 아래서부터 채워준다.

 

 

 

[코드]

 

시간 : 0ms

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;

struct pos{
    int x,y;
};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int map[12][6]={0,};

void solve()
{
    vector <int> v;

    for(int i=0;i<6;i++)
    {
        for(int j=11;j>=0;j--){
            if(map[j][i] != 0 ) v.push_back(map[j][i]);
            map[j][i]=0;
        }
        
        int idx = 11;
        for(int j=0;j<v.size();j++) map[idx--][i]=v[j];
        v.clear();
    }
}

bool BFS()
{
    bool check = false;
    vector <pos> v;

    int visited[12][6]={0,};
    queue <pos> q;
    int num =0;
    
    for(int i=0;i<12;i++){
        for(int j=0;j<6;j++){
            
            if(map[i][j] != 0 && visited[i][j] == 0 ){
                num=1;
                q.push({i,j});
                visited[i][j]=1;
                v.push_back({i,j});
            }
            
            while(!q.empty()){
                
                int x = q.front().x;
                int y = q.front().y;
                q.pop();
                
                for(int k=0;k<4;k++){
                    
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    
                    if(nx < 0 || ny <0 || nx >= 12 || ny >= 6 || visited[nx][ny] != 0)  continue;
                    if(map[x][y] != map[nx][ny] )   continue;
                    q.push({nx,ny});
                    v.push_back({nx,ny});
                    visited[nx][ny] = 1;
                }
            }
            
            if(v.size() >=4){
                for(int k=0;k<v.size();k++)
                    map[v[k].x][v[k].y]=0;
                check=true;
            }
            v.clear();
        }
    }
    
    return check;
}

int main(void)
{
    for(int i=0;i<12;i++){
        for(int j=0;j<6;j++){
            char ch1;
            cin >> ch1;
            if(ch1 == '.')  map[i][j] = 0;
            else if(ch1 == 'R')  map[i][j] = 1;
            else if(ch1 == 'G')  map[i][j] = 2;
            else if(ch1 == 'B')  map[i][j] = 3;
            else if(ch1 == 'P')  map[i][j] = 4;
            else if(ch1 == 'Y')  map[i][j] = 5;
        }
    }
    int cnt =0;
    
    while(1){
        if(!BFS())    break;
        solve();
        cnt++;
    }
    
    cout << cnt;
    return 0;
    
}