미네랄

*클러스터들을 하나의 영역으로 보고 번호를 라벨링하여 구분했음 

*클러스터끼리 인접해있다면 내려가지 않음 

*내려가는 칸의 수는 min(바닥과의 높이 차, 다른 클러스터와의 차이)

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
int r, c, n;
char map[101][101];
typedef pair<int, int> pp;
typedef pair<pp, pp> pppp;
 
int visited[101][101];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
 
void print()
{
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cout << map[i][j];
        }
        cout << '\n';
    }
}
void drawCluster(int label, int cnt)
{
 
    while (cnt--)
    {
        for (int i = r - 1; i >= 0; i--)
        {
            for (int j = c - 1; j >= 0; j--)
            {
                if (visited[i][j] != label)
                {
                    continue; //해당 클러스터가 아님
                }
                else
                {
                    map[i + 1][j] = map[i][j];
                    map[i][j] = '.';
                    visited[i + 1][j] = visited[i][j];
                    visited[i][j] = 0;
                }
            }
        }
    }
}
void checkCluster(int label)
{
    //클러스터들을 끌어내려준다. (내려올 수 있는 것들만)
    for (int i = 1; i <= label; i++)
    {
        //해당 클러스터 넘버에 맞는 것들이 공중에 얼마나 떠있는지 확인
        //동시에 두 개의 클러스터가 내려올 확률은 없기 때문에 하나만 찾으면 된다.
        bool flag = false;
        int idxx = 101;
        for (int k = 0; k < c; k++)
        {
            for (int j = r - 1; j >= 0; j--)
            {
                if (visited[j][k] != i)
                    continue; //찾는 클러스터가 아님
                else
                {
                    //바닥과 마주해있거나, 다른 클러스터와 붙어있음
                    if (j == r - 1 || (visited[j + 1][k] != i && visited[j + 1][k]))
                    {
                        flag = true;
                        break;
                    }
                    idxx = min(idxx, r - (j+1));
 
                    for (int z = j + 1; z < r; z++)
                    {
                        if (visited[z][k] != i && visited[z][k])
                        {
                            idxx = min(idxx, z - j - 1);
                            break;
                        }
                    }
                }
            }
            if (flag)
                break;
        }
        if (!flag)
        {
            //내려올게 있음
            drawCluster(i, idxx);
        }
        
    }
}
void dfs(int x, int y, int label)
{
    if (visited[x][y])
        return;
    visited[x][y] = label;
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || nx >= r || ny < 0 || ny >= c || visited[nx][ny] || map[nx][ny] == '.')
            continue;
 
        dfs(nx, ny, label);
    }
}
 
int numberingCluster()
{
    int label = 0;
 
    for (int i = r - 1; i >= 0; i--)
    {
        for (int j = c - 1; j >= 0; j--)
        {
            if (!visited[i][j] && map[i][j] == 'x')
            {
 
                ++label;
                dfs(i, j, label);
            }
        }
    }
    return label;
}
void throwBar(int h, int dir)
{
    queue<pp> q;
 
    if (dir % 2)
    {
        //오른쪽에서 왼쪽으로
        for (int i = c - 1; i >= 0; i--)
        {
            if (map[h][i] == 'x')
            {
                //미네랄이 있으면
                //클러스터가 끊기고 주변의 클러스터가 밑으로 끌어내려질 수 있는지 확인하낟.
                map[h][i] = '.';
                return;
            }
        }
    }
    else
    {
        for (int i = 0; i < c; i++)
        {
            if (map[h][i] == 'x')
            {
                //미네랄이 있으면
                //클러스터가 끊기고 주변의 클러스터가 밑으로 끌어내려질 수 있는지 확인하낟.
                map[h][i] = '.';
 
                return;
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> map[i][j];
        }
    }
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
 
        memset(visited, 0, sizeof(visited));
        throwBar(r - tmp, i);
        int label = numberingCluster();
 
        checkCluster(label);
    }
    print();
 
    return 0;
}

 

도움이 된 TC

10 20
..xxxxxxxxxxxxxxx... 
..x.............x... 
..x.............x... 
..x.............x... 
..x.............x... 
..x.............x... 
..x.............x... 
..xxxxxx........x... 
................x... 
x...............x... 
2
1 7