[백준 알고리즘] 2933번 - 미네랄 (구현, BFS)

1. 개요

2시간 녹인 문제... 늘 내 블로그에 적는 말이지만 구현은 초반 설계가 잘못된다면 정말 힘든 문제인 것 같다. 여러 예외도 생각해야하고... 이래서 난이도 높은 문제들은 구현인가...? 싶기도 하다. 문제를 나누고 나올 수 있는 예외를 전부 처리해야 성공하는 문제이기에 시간도 많이 들고 힘도 많이 들었다...

 

출처: https://www.acmicpc.net/problem/2933

---

 

---

2. 본문

내가 생각한 구현 문제의핵심은 다음과 같다. 물론 말 그대로 타고난 능력이 좋은 사람들은 저런 방법이 필요 없겠지만 말이다.. ㅋㅋㅋ

---

1. 문제를 단계별로 나눈다.

2. 예외사항을 처리한다.

3. 구현

---

- 문제 나누기

 

문제를 나누면 다음과 같다.

---

1. 방향에 맞는 미네랄 제거.

2. 떨어지는 미네랄 조사.

3. 떨어질 미네랄이 있다면 떨어뜨리기.

---

- 예외사항 처리

 

일단 내가 걸린 예외사항은 다음과 같이 바닥이 아닌 곳에서 멈추는 경우이다.

---

---

이렇게 되면 새로운 클러스터와 합쳐질 때 까지 떨어져야한다.

---

---

자 그럼 다시 문제를 세분화해서 나누면 다음과 같다.

---

1. 미네랄 제거.

2. 떨어지는 미네랄 찾기.

3. 미네랄이 떨어질 거리 찾기.

4. 찾은 거리만큼 클러스터 떨어뜨리기.

---

- 구현

 

미네랄 지우는 함수

void erase_minaral(bool dir, int high)
{
    // left
    if (dir)
    {

        for (int i = 0; i < C; i++)
        {
            if (cave[high][i] == 'x')
            {
                cave[high][i] = '.';
                return;
            }
        }
    }
    else
    {

        for (int i = C - 1; i > -1; i--)
        {
            if (cave[high][i] == 'x')
            {
                cave[high][i] = '.';
                return;
            }
        }
    }
}

 

클러스터 떨어뜨리기

void fall_clusters()
{

    pair<int, int> fall_clusters_pos = get_fall_clusters();

    if(fall_clusters_pos.first != -1 && fall_clusters_pos.second != -1){
        adjust_one_cluster(fall_clusters_pos);
    }
}

 

클러스터를 떨어뜨리는 함수는 먼저 떨어질 클러스터를 조사하고, 만약 떨이질 클러스터가 있다면 거리를 구해 조정하는 역할을 한다.

 

떨어지는 클러스터는 BFS를 사용해 탐색하고 가장 아래의 행의 위치가 마지막 행이 아니라면 떨어질 클러스터라고 판단한다. 다음은 탐색 코드이다.

 

떨어지는 클러스터 찾는 코드

pair<int, int> get_fall_clusters()
{
    bool visited[105][105] = {0};
    pair<int, int> pos = {-1, -1};

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (cave[i][j] == 'x' && !visited[i][j])
            {
                int min_row = -1;
                int start_row = i;
                int start_col = j;
                queue<pair<int, int>> q;

                visited[i][j] = true;
                q.push(make_pair(i, j));

                while (!q.empty())
                {
                    int curr_row = q.front().first;
                    int curr_col = q.front().second;
                    q.pop();

                    min_row = max(min_row, curr_row);

                    for (int k = 0; k < 4; k++)
                    {
                        int new_row = curr_row + dir_x[k];
                        int new_col = curr_col + dir_y[k];

                        if (new_row >= 0 && new_row < R && new_col >= 0 && new_col < C && cave[new_row][new_col] == 'x' && !visited[new_row][new_col])
                        {
                            visited[new_row][new_col] = true;
                            q.push(make_pair(new_row, new_col));
                        }
                    }
                }

                if (min_row != R - 1)
                {
                    return make_pair(start_row, start_col);
                }
            }
        }
    }

    return pos;
}

 

클러스터 떨어뜨리는 코드

void adjust_one_cluster(pair<int, int> fall_clusters_pos)
{
    int visited[105][105] = {0};
    queue<pair<int, int>> q;
    int min_row = -1;

    visited[fall_clusters_pos.first][fall_clusters_pos.second] = true;
    q.push(make_pair(fall_clusters_pos.first, fall_clusters_pos.second));

    while (!q.empty())
    {
        int curr_row = q.front().first;
        int curr_col = q.front().second;
        q.pop();

        for (int k = 0; k < 4; k++)
        {
            int new_row = curr_row + dir_x[k];
            int new_col = curr_col + dir_y[k];

            if (new_row >= 0 && new_row < R && new_col >= 0 && new_col < C && cave[new_row][new_col] == 'x' && !visited[new_row][new_col])
            {
                visited[new_row][new_col] = true;
                q.push(make_pair(new_row, new_col));
            }
        }
    }

    int dis = R;

    for(int col = 0; col < C; col++){
        int max_row = -1;
        for(int row = 0; row < R; row++){
            
            if(visited[row][col] && !visited[row + 1][col]){
                int end_row = -1;

                for(end_row = row + 2; end_row < R; end_row++){

                    if((!visited[end_row][col] && cave[end_row][col] == 'x') ){
                        dis = min(dis, end_row - row - 1);
                        break;
                    }

                    if( (cave[end_row][col] == '.' && end_row == R - 1)){
                        dis = min(dis, end_row - row );
                        break;
                    }


                }
            }
        }
    }

    for (int i = R - 1; i >= 0; i--)
    {
        for (int j = 0; j < C; j++)
        {
            if (visited[i][j])
            {
                cave[i + dis][j] = 'x';
                cave[i][j] = '.';
            }
        }
    }
}

 

다음은 전체 코드이다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int R, C;
string cave[105];
int highs[105] = {0};
int N;
int dir_x[4] = {0, 1, 0, -1};
int dir_y[4] = {1, 0, -1, 0};

void erase_minaral(bool dir, int high)
{
    // left
    if (dir)
    {

        for (int i = 0; i < C; i++)
        {
            if (cave[high][i] == 'x')
            {
                cave[high][i] = '.';
                return;
            }
        }
    }
    else
    {

        for (int i = C - 1; i > -1; i--)
        {
            if (cave[high][i] == 'x')
            {
                cave[high][i] = '.';
                return;
            }
        }
    }
}

pair<int, int> get_fall_clusters()
{
    bool visited[105][105] = {0};
    pair<int, int> pos = {-1, -1};

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (cave[i][j] == 'x' && !visited[i][j])
            {
                int min_row = -1;
                int start_row = i;
                int start_col = j;
                queue<pair<int, int>> q;

                visited[i][j] = true;
                q.push(make_pair(i, j));

                while (!q.empty())
                {
                    int curr_row = q.front().first;
                    int curr_col = q.front().second;
                    q.pop();

                    min_row = max(min_row, curr_row);

                    for (int k = 0; k < 4; k++)
                    {
                        int new_row = curr_row + dir_x[k];
                        int new_col = curr_col + dir_y[k];

                        if (new_row >= 0 && new_row < R && new_col >= 0 && new_col < C && cave[new_row][new_col] == 'x' && !visited[new_row][new_col])
                        {
                            visited[new_row][new_col] = true;
                            q.push(make_pair(new_row, new_col));
                        }
                    }
                }

                if (min_row != R - 1)
                {
                    return make_pair(start_row, start_col);
                }
            }
        }
    }

    return pos;
}

void adjust_one_cluster(pair<int, int> fall_clusters_pos)
{
    int visited[105][105] = {0};
    queue<pair<int, int>> q;
    int min_row = -1;

    visited[fall_clusters_pos.first][fall_clusters_pos.second] = true;
    q.push(make_pair(fall_clusters_pos.first, fall_clusters_pos.second));

    while (!q.empty())
    {
        int curr_row = q.front().first;
        int curr_col = q.front().second;
        q.pop();

        for (int k = 0; k < 4; k++)
        {
            int new_row = curr_row + dir_x[k];
            int new_col = curr_col + dir_y[k];

            if (new_row >= 0 && new_row < R && new_col >= 0 && new_col < C && cave[new_row][new_col] == 'x' && !visited[new_row][new_col])
            {
                visited[new_row][new_col] = true;
                q.push(make_pair(new_row, new_col));
            }
        }
    }

    int dis = R;

    for(int col = 0; col < C; col++){
        int max_row = -1;
        for(int row = 0; row < R; row++){
            
            if(visited[row][col] && !visited[row + 1][col]){
                int end_row = -1;

                for(end_row = row + 2; end_row < R; end_row++){

                    if((!visited[end_row][col] && cave[end_row][col] == 'x') ){
                        dis = min(dis, end_row - row - 1);
                        break;
                    }

                    if( (cave[end_row][col] == '.' && end_row == R - 1)){
                        dis = min(dis, end_row - row );
                        break;
                    }


                }
            }
        }
    }

    for (int i = R - 1; i >= 0; i--)
    {
        for (int j = 0; j < C; j++)
        {
            if (visited[i][j])
            {
                cave[i + dis][j] = 'x';
                cave[i][j] = '.';
            }
        }
    }
}

void fall_clusters()
{

    pair<int, int> fall_clusters_pos = get_fall_clusters();

    if(fall_clusters_pos.first != -1 && fall_clusters_pos.second != -1){
        adjust_one_cluster(fall_clusters_pos);
    }
}

int main(void)
{

    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        cin >> cave[i];
    }
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> highs[i];
    }

    for (int i = 0; i < N; i++)
    {
        erase_minaral(i % 2 == 0, R - highs[i]);
        fall_clusters();
    }

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cout << cave[i][j];
        }
        cout << '\n';
    }

    return 0;
}

 

3. 결어

2시간 박살난 코드... 실전에서 만났으면 난 떨어졌을 것 같다... 하... 아무리 해도 적응이 안되는 문제이긴하다.