[C++] 백준 2933 미네랄

 
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
 
bool bVisit[101][101] = {};
int iDirX[4] = { 1,-1,0,0 };
int iDirY[4] = { 0,0,1,-1 };
// 높이
int R = 0;
// 길이
int C = 0;
 
void Down(std::vector<std::string>& vec)
{
    int iMaxNumber = 1;
 
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            if (bVisit[i][j])
                vec[i][j] = '.';
        }
    }
 
    while (true)
    {
        bool bCan = true;
        ++iMaxNumber;
 
        for (int i = 0; i < R; ++i)
        {
            for (int j = 0; j < C; ++j)
            {
                if (bVisit[i][j])
                {
                    if (i + iMaxNumber < vec.size())
                    {
                        if (vec[i + iMaxNumber][j] == 'x')
                        {
                            bCan = false;
                            break;
                        }
                    }
 
                    else
                    {
                        bCan = false;
 
                        break;
                    }
                }
 
            }
 
            if (!bCan)
                break;
        }
 
 
        if (bCan)
            continue;
 
        else
        {
            --iMaxNumber;
            break;
        }
    }
 
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            if (bVisit[i][j])
                vec[i + iMaxNumber][j] = 'x';
        }
    }
 
    memset(bVisit, false, sizeof(bVisit));
}
 
// 바닥이랑 연결되어있는가 검색
bool Check(std::vector<std::string> vec, int iRow, int iCol)
{
    if (iRow < 0 || iRow >= vec.size() || iCol < 0 || iCol >= vec[iRow].size() ||
        vec[iRow][iCol] == '.' || bVisit[iRow][iCol])
        return false;
 
    bool bSubvisit[101][101] = {};
 
    int iFloor = vec.size() - 1;
    std::queue<std::pair<int, int>> que = {};
    que.push({ iRow, iCol });
    bSubvisit[iRow][iCol] = true;
 
    while (!que.empty())
    {
        int iX = que.front().first;
        int iY = que.front().second;
        que.pop();
 
        if (iX == iFloor)
            return false;
 
        for (int i = 0; i < 4; ++i)
        {
            int iNextX = iX + iDirX[i];
            int iNextY = iY + iDirY[i];
 
            if (iNextX >= 0 && iNextX < vec.size() &&
                iNextY >= 0 && iNextY < vec[0].size())
            {
                if (!bSubvisit[iNextX][iNextY] && vec[iNextX][iNextY] == 'x')
                {
                    bSubvisit[iNextX][iNextY] = true;
                    que.push({ iNextX, iNextY });
                }
            }
        }
    }
 
    for (int i = 0; i < vec.size(); ++i)
    {
        for (int j = 0; j < vec[i].size(); ++j)
        {
            if (bSubvisit[i][j])
                bVisit[i][j] = true;
        }
    }
 
    return true;
}
 
int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cin >> R >> C;
    std::vector<std::string> vec(R, "");
 
    for (int i = 0; i < R; ++i)
    {
        std::cin >> vec[i];
    }
 
    int N = 0;
    std::cin >> N;
 
    bool bLeft = true;
 
    for (int i = 0; i < N; ++i)
    {
        bool bCheck = false;
        int iHeight = -1;
        int iBreak = -1;
        std::cin >> iHeight;
 
        if (bLeft)
        {
            for (int j = 0; j < C; ++j)
            {
                if (vec[R - iHeight][j] == 'x')
                {
                    vec[R - iHeight][j] = '.';
                    iBreak = j;
                    break;
                }
            }
        }
 
        else
        {
            for (int j = C - 1; j >= 0; --j)
            {
                if (vec[R - iHeight][j] == 'x')
                {
                    vec[R - iHeight][j] = '.';
                    iBreak = j;
                    break;
                }
            }
        }
 
        if (iBreak != -1)
        {
            if (Check(vec, R - iHeight - 1, iBreak))
                bCheck = true;
 
            if (bLeft)
            {
                if (Check(vec, R - iHeight, iBreak + 1))
                    bCheck = true;
            }
 
            else
            {
                if (Check(vec, R - iHeight, iBreak - 1))
                    bCheck = true;
            }
 
            if (Check(vec, R - iHeight + 1, iBreak))
                bCheck = true;
        }
 
        if (bCheck)
            Down(vec);
 
        bLeft = !bLeft;
    }
 
    for (int i = 0; i < R; ++i)
    {
        std::cout << vec[i];
 
        if (i != R -1)
            std::cout << "\n";
    }
 
    return 0;
}
 

구현에 진짜 애를 먹었습니다.

여러가지를 생각했어야 했는데 단면만 보고 풀어서...

처음에는 던지는 방향 한개와 그 위만 검색했는데 아래도 떨어질 수 있다는 걸 판단못했고

두번째로는 밑바닥만 붙으면 되겠지라는 생각으로 풀었더니 위에서 걸렸다면 더 떨어지지 못한다라는 생각을 못했습니다...

생각을 좀 오래했어야 했었네요.