백준 11559. Puyo Puyo (구현)

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

11559번: Puyo Puyo

같은 뿌요가 4개이상 상하좌우로 연결되어있으면, 터트리고, 중력작용해서 밑으로 내린다. 이를 더이상 터트릴게 없을때까지 반복한다.  

 

1. 특징

1) BFS

2) 구현 

 

2.  삽질 포인트

1) bfs: bfs 사용할 때, 맨날 실수한다. 정말 한번에 제대로 구현한 적이 별로 없는 거 같다. 

for(int i = 0; i < x; i++)
    {
        for(int j = 0; j < y; j++)
        {
            if(board[i][j] != '.' && visited[i][j] == 0) 
            {
                int cnt = 1;
                queue<pair<int, int> > _queue;
                vector<pair<int, int> > _vec;
                _queue.push(make_pair(i, j));
                _vec.push_back(make_pair(i, j));
                visited[i][j] = 1;
                while(!_queue.empty())
                {
                    auto cur = _queue.front();
                    _queue.pop();

                    for(int dir = 0; dir < 4; dir++)
                    {
                        int nx = cur.first + dx[dir]; // int nx = i + dx[dir]; 로 작성함. 
                        int ny = cur.second + dy[dir]; // int ny = j + dy[dir];

                        if(nx < 0 || nx >= x || ny < 0 || ny >= y) continue;
                        if(visited[nx][ny] != 0) continue; // 이 부분 빼먹음
                        if(board[cur.first][cur.second] != board[nx][ny]) continue; // board[i][j] != ... 로 작성함
                        cnt += 1;
                        visited[nx][ny] = visited[cur.first][cur.second] + 1; // = visited[i][j]으로 작성함
                        _queue.push(make_pair(nx, ny));
                        _vec.push_back(make_pair(nx, ny));
                    }
                }

            }
        }
    }

 

3.  구현 포인트

1) bfs

2) 중력 적용

void gravityfunc()
{
    for(int j = 0; j < y; j++)
    {
        int cnt = 0;
        for(int i = x-1; i >= 0; i--)
        {
            if(board[i][j] == '.') { cnt++; }
            else
            {
                if(cnt == 0) continue;
                board[i + cnt][j] = board[i][j];
                board[i][j] = '.';
            }
        }
    }
}

 

4. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <set>
#include <cstring>
#include <string>
#include <stdio.h>
#include <limits.h>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <sstream>
//#include <bits/stdc++.h>
using namespace std;

int x;
int y;
string board[12];
int ans;
int dx[4] = {0, 0, 1, -1}; //우 좌 위 아래
int dy[4] = {1, -1, 0, 0};
int visited[13][7];

void Initvisit()
{
    for(int i = 0; i < x; i++)
    {
        fill(visited[i], visited[i] + y, 0);
    }
}
void printFunc()
{
    for(int i = 0; i < 12; i++)
    {
        for(int j = 0; j < 6; j++)
        {
            cout << board[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << '\n';
}


bool bombfunc()
{
    bool isBomb = false;
    Initvisit();
    
    for(int i = 0; i < x; i++)
    {
        for(int j = 0; j < y; j++)
        {
            if(board[i][j] != '.' && visited[i][j] == 0) // 뿌요이면, bfs
            {
                int cnt = 1;
                queue<pair<int, int> > _queue;
                vector<pair<int, int> > _vec;
                _queue.push(make_pair(i, j));
                _vec.push_back(make_pair(i, j));
                visited[i][j] = 1;
                while(!_queue.empty())
                {
                    auto cur = _queue.front();
                    _queue.pop();

                    for(int dir = 0; dir < 4; dir++)
                    {
                        int nx = cur.first + dx[dir];
                        int ny = cur.second + dy[dir];

                        if(nx < 0 || nx >= x || ny < 0 || ny >= y) continue;
                        if(visited[nx][ny] != 0) continue;
                        if(board[cur.first][cur.second] != board[nx][ny]) continue; // 뿌요가 다른 거면 나감
                        
                        cnt += 1;
                        visited[nx][ny] = visited[cur.first][cur.second] + 1;
                        _queue.push(make_pair(nx, ny));
                        _vec.push_back(make_pair(nx, ny));
                    }
                }

                if(cnt >= 4)
                {
                    isBomb = true;
                    for(int i = 0; i < cnt; i++)
                    {
                        int curx = _vec[i].first;
                        int cury = _vec[i].second;

                        board[curx][cury] = '.';
                    }
                }
            }
        }
    }


    return isBomb;

}

void gravityfunc()
{
    
    for(int j = 0; j < y; j++)
    {
        int cnt = 0;
        for(int i = x-1; i >= 0; i--)
        {
            if(board[i][j] == '.')
            {
                cnt++;
            }
            else
            {
                if(cnt == 0) continue;
                board[i + cnt][j] = board[i][j];
                board[i][j] = '.';
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    x = 12;
    y = 6;

    for(int i = 0; i < x; i++)
    {
        cin >> board[i];
    }
    bool isBomb = false;

    while(true)
    {
        // 연쇄 처리 
        isBomb = bombfunc();
        if(isBomb == false) break;
        else ans+=1;
        //printFunc();
        
        // 중력 처리
        gravityfunc();
        // printFunc();
    }

    cout << ans;
}