[ 백준 2933 ] 미네랄 (C++)

백준의 미네랄(2933) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 시뮬레이션이 주가 되는 문제라서 구현방법으로 바로 들어가보자.

   먼저 2명의 사람이 번갈아 가면서 정해진 높이에 막대기를 던지게 된다.

   막대기가 날아가면서 미네랄에 맞게 되는 순간, 미네랄을 깨지게 된다. 이 부분까지는 쉽게 구현할 수 있을 것이다.

   이 후, 클러스터 라는 존재가 나오게 되는데 클러스터는 쉽게 말해서 미네랄 덩어리를 의미하게 된다.

   클러스터는 절대 공중으로 떠 있을 수가 없다. 즉, 막대기를 던지는 과정에서 미네랄이 깨지게 되고, 이 미네랄이

   포함되어 있는 클러스터가 공중에 뜨는 경우가 발생하게 된다.

   그렇다면 공중에 떠있다는 것을 어떻게 확인할 수 있을까?? 바로 땅바닥이랑 연결이 안되있으면 공중에 떠있는 것이다.

   그래서 본인은 이 부분을 BFS탐색을 통해서 체크를 해주었다. 가장 아랫줄이면서 미네랄이 존재하는 좌표부터

   상하좌우로 탐색을 하면서 연결되어 있는 모든 미네랄들을 Visit[][] 배열을 통해서 체크를 해주었다.

   즉, 모든 탐색이 끝난 후에도 Visit배열이 false인 미네랄들은, 공중에 떠 있다는 의미가 되고 이 미네랄들을

   내려주었다.

   이 부분에 대한 코드를 설명하자면 다음과 같다.

bool Cluster_In_Air()        // 공중에 있는 클러스터들을 판단하기 위한 함수
{
    for (int i = 0; i < C; i++)    // 땅바닥에 있는 미네랄들만 BFS탐색 실행
    {
        if (MAP[R - 1][i] == 'x' && Visit[R - 1][i] == false)    // 미네랄이면서 아직 방문하지 않은 곳이면
        {
            BFS(R - 1, i);    // BFS 탐색 실행
        }
    }

    bool CIA = false;

    memset(Cluster, false, sizeof(Cluster));

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (MAP[i][j] == 'x' && Visit[i][j] == false)    // 공중에 떠있는 미네랄들은
            {
                CIA = true;
                Air_Cluster.push_back(make_pair(i, j));    // 따로 Vector에 좌표를 저장
                Cluster[i][j] = true;                    // Cluster라는 배열에 따로 표시
            }
        }
    }
    return CIA;
}

   이후 단계는 공중에 떠있는 클러스트들을 땅바닥과 연결된 다른 클러스터들과 합쳐주면 되는데 그 과정은

   다음과 같이 구현할 수 있다.

   아 구현방법을 말하기 전에, 우리는 위의 코드에서 공중에 떠있는 클러스틀만, Cluster[][] 라는 2차원 배열에

   표시를 해 주었다 !

void Remake_MAP()
{
    int H = INF - 1;
    for (int i = 0; i < Air_Cluster.size(); i++)    // 공중에 떠있는 클러스터들의 좌표가 저장된 벡터
    {
        int x = Air_Cluster[i].first;            // x좌표
        int y = Air_Cluster[i].second;        // y좌표
        
        int Temp_H = Gravity(x, y);        // 밑에 함수 참고 !
        if (Temp_H == INF) continue;
        else H = Min(H, Temp_H);            // 내릴 수 있는 최소값 갱신 !
    }

    sort(Air_Cluster.begin(), Air_Cluster.end());    // 가장 아래쪽에 있는 클러스터 부터 내리기 위해서
    for (int i = Air_Cluster.size() - 1; i >= 0; i--)
    {
        int x = Air_Cluster[i].first;
        int y = Air_Cluster[i].second;

        MAP[x][y] = '.';
        MAP[x + H][y] = 'x';
    }
}

int Gravity(int x, int y)
{
    int Cnt = 0;
    for (int i = x + 1; i < R; i++)    // 가장 바닥까지 쭉 내려보면서
    {
        if (MAP[i][y] == 'x')    // 중간에 다른 미네랄을 만났는데
        {
            if (Cluster[i][y] == true) return INF;

             // 만약 그 미네랄이 같이 공중에 있는 클러스터라면

           // 이 미네랄은 얼마나 떨어져야 하는지 결정하는데 영향을 못미친다.
            else return Cnt;

           // 만약 그 미네랄이 공중에 떠있는 클러스터가 아닌 다른 클러스터라면

           // 내릴 수 있는 칸수를 return

        }
        else if (MAP[i][y] == '.') Cnt++;

        // 만약 '.' 이라면 내릴 수 있으므로 Cnt++

    }
    return Cnt;
}

     나머지 부분에 대해서는 소스코드를 참고하자 !

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 100
#define INF 987654321
using namespace std;
 
int R, C, N;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool Cluster[MAX][MAX];
vector<int> Order;
vector<pair<int, int>> Air_Cluster;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    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 a; cin >> a;
        Order.push_back(a);
    }
}
 
bool Throw_Stick(int H, char ch)
{
    if (ch == 'L')
    {
        for (int i = 0; i < C; i++)
        {
            if (MAP[H][i] == 'x')
            {
                MAP[H][i] = '.';
                return true;
            }
        }
    }
    else
    {
        for (int i = C - 1; i >= 0; i--)
        {
            if (MAP[H][i] == 'x')
            {
                MAP[H][i] = '.';
                return true;
            }
        }
    }
    return false;
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < R && ny < C)
            {
                if (MAP[nx][ny] == 'x' && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
bool Cluster_In_Air()
{
    for (int i = 0; i < C; i++)
    {
        if (MAP[R - 1][i] == 'x' && Visit[R - 1][i] == false)
        {
            BFS(R - 1, i);
        }
    }
 
    bool CIA = false;
 
    memset(Cluster, false, sizeof(Cluster));
 
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (MAP[i][j] == 'x' && Visit[i][j] == false)
            {
                CIA = true;
                Air_Cluster.push_back(make_pair(i, j));
                Cluster[i][j] = true;
            }
        }
    }
    return CIA;
}
 
int Gravity(int x, int y)
{
    int Cnt = 0;
    for (int i = x + 1; i < R; i++)
    {
        if (MAP[i][y] == 'x')
        {
            if (Cluster[i][y] == true) return INF;
            else return Cnt;
        }
        else if (MAP[i][y] == '.') Cnt++;
    }
    return Cnt;
}
 
void Remake_MAP()
{
    int H = INF - 1;
    for (int i = 0; i < Air_Cluster.size(); i++)
    {
        int x = Air_Cluster[i].first;
        int y = Air_Cluster[i].second;
        
        int Temp_H = Gravity(x, y);
        if (Temp_H == INF) continue;
        else H = Min(H, Temp_H);
    }
 
    sort(Air_Cluster.begin(), Air_Cluster.end());
    for (int i = Air_Cluster.size() - 1; i >= 0; i--)
    {
        int x = Air_Cluster[i].first;
        int y = Air_Cluster[i].second;
 
        MAP[x][y] = '.';
        MAP[x + H][y] = 'x';
    }
}
 
void Solution()
{
    for (int i = 0; i < Order.size(); i++)
    {
        Air_Cluster.clear();
        memset(Visit, false, sizeof(Visit));
        memset(Cluster, false, sizeof(Cluster));
 
        char Order_C;
        int Height = Order[i];
        Height = R - Height;
 
        if (i % 2 == 0) Order_C = 'L';
        else Order_C = 'R';
        
        if (Throw_Stick(Height, Order_C) == false) continue;
    
        if (Cluster_In_Air() == false) continue;
        else Remake_MAP();
    }
 
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cout << MAP[i][j];
        }
        cout << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}