16768, Gold 4

16768번: Mooyo Mooyo

문제

• 같은 숫자가 $k$개 이상 인접하면 사라지고 아래로 내려온다. 최종 모습은?

 

풀이

※ 마킹한 1은 미리 0으로 바꾸지 않는다(변화는 항상 마지막에)
화살표를 따라가다가 0을 만나면 열을 바꾸도록 설계되었기 때문에 아래와 같은경우 제대로 동작하지 않는다

이런식으로 구성되면 2에서 bfs 진행x

인접한 $k$개 이상의 수를 모두 찾으면 모두 0으로 바꾸고 모두 아래로 내린다(반복)

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n, k;
 
bool pop_hey(vector<vector<int> >& d)
{
    vector<vector<int> > visited(n, vector<int>(10));
    stack<pii> will_pop;
 
    for(int c = 0; c < 10; c++){
        for(int r = n-1; r >= 0; r--){
            if(d[r][c] == 0) continue;
 
            if(!visited[r][c]){
                visited[r][c] = 1;
                int color = d[r][c];
                stack<pii> adj;
                queue<pii> q;
 
                adj.push({r, c});
                q.push({r, c});
 
                while(!q.empty()){
                    auto cur = q.front(); q.pop();
                    ooop(i, 4){
                        int nr = cur.first + "0121"[i] - '1';
                        int nc = cur.second + "1210"[i] - '1';
                        if(nr < 0 || nr >= n || nc < 0 || nc >= 10) continue;
                        if(!visited[nr][nc] && d[nr][nc] == color){
                            visited[nr][nc] = 1;
                            q.push({nr, nc});
                            adj.push({nr, nc});
                        }
                    }
                }
 
                if(adj.size() >= k){
                    while(!adj.empty()){
                        will_pop.push(adj.top());
                        adj.pop();
                    }
                }
 
            }
 
        }
    }
 
    if(will_pop.empty()) return false;
    else{
        while(!will_pop.empty()){
            auto cur = will_pop.top(); will_pop.pop();
            d[cur.first][cur.second] = 0;
        }
        return true;
    }
}
 
void gravity(vector<vector<int> >& d)
{
    for(int c = 0; c < 10; c++){
        int empty = 0;
        for(int r = n-1; r >= 0; r--){
            if(d[r][c] == 0) {
                empty = r;
                break;
            }
        }
 
        if(empty){
            for(int r = empty-1; r >= 0; r--) {
                if (d[r][c]) {
                    swap(d[empty][c], d[r][c]);
                    empty--;
                }
            }
 
        }
    }
 
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
    vector<vector<int> > d(n, vector<int>(10));
 
    string s;
    ooop(r, n){
        cin >> s;
        ooop(c, 10) d[r][c] = s[c] - '0';
    }
 
    while(pop_hey(d))  gravity(d);
 
    ooop(r, n){
        ooop(c, 10) cout << d[r][c];
        cout << endl;
    }
 
    return 0;
}cs