백준 2933 - 미네랄(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2933

2933번: 미네랄

구현력을 요구하는 BFS 문제였습니다.

두 사람이 좌우에서 막대기를 던지면서 미네랄를 부술때, 마지막의 미네랄 모양을 구하는 모습입니다.

문제에서 주어진 조건을 보면

1. 좌 -> 우 -> 좌 와 같이 돌아가면서 던진다.

2. 아래층이 1이며 윗층이 N이다.

3. 떨어지는 클러스터는 1개이다.

해당 조건을 기본적으로 알고 문제를 접근해보겠습니다.

 

문제를 크게 나누면 3개로 나눌 수 있습니다.

1. 미네랄 부수기

2. 클러스터 찾기

3. 클러스터 내리기

 

먼저 미네랄를 부수는 파트부터 확인하겠습니다.

void break_mineral(int x, int dir){
    if(dir % 2 == 0){
        int y = 1;
        while(1){
            if(y > M) break;
            if(map[N-x+1][y] == 'x'){
                map[N-x+1][y] = '.';
                break;
            }
            y++;
        }
    }
    else{
        int y = M;
        while(1){
            if(y < 1) break;
            if(map[N-x+1][y] == 'x'){
                map[N-x+1][y] = '.';
                break;
            }
            y--;
        }
    }
}

미네랄을 부술 때, 어느 높이에서 부실지는 입력에서 주어집니다. 

따라서 우리가 확인해야할 것은, 이번에 부술 위치가 왼쪽, 오른쪽 중에 어디인지입니다.

함수에서 dir변수를 보면, 몇 번째로 부수는 미네랄인지 값을 받아옵니다.

dir값이 0, 2, 4...와 같은 짝수라면 왼쪽, 아니라면 오른쪽이라는 것을 확인할 수 있습니다.

 

다음은 높이입니다. map 배열에서는 윗층이 1부터 시작하지만, 미네랄은 윗층이 N이기에 높이를 전환해줘야합니다.

높이를 전환해줬다면, 반복문을 이용해 해당 높이에서 미네랄이 처음으로 나오는 위치를 찾은 뒤, 부셔주면 됩니다.

 

 

공중에 떠있는 클러스터를 찾는 부분입니다.

bool find_float_cluster(){
    bool can = false; // 공중에 떠있는 미네랄이 없는 경우, false를 return 해준다.
    for(int i = 1; i <= M; i++){
        if(check[N][i] == 0 && map[N][i] == 'x') bfs(N, i);
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(map[i][j] == 'x' && check[i][j] == 0){ // 공중에 떠있는 미네랄
                Move.push_back({i,j}); // 움직이기 위해 좌표를 저장한다.
                can = true;
            }
        }
    }
    return can;
}

공중에 떠있는 클러스터가 바닥으로 떨어진다고 문제에서 주어졌습니다.

그렇다면, 바닥에 있는 미네랄을 찾은 뒤, 해당 미네랄에서 상하좌우로 연결된 미네랄을 전부 찾아준다면, 찾지 못한 미네랄들은 공중에 떠있는 클러스터가 될 것입니다.

따라서, map 배열에서 값이 'x' 이지만, check 배열에서 값이 0 이라면, 공중에 떠있는 미네랄인 것입니다.

 

이들을 내려주기 위해, vector에 입력해줬습니다.

 

 

마지막으로 클러스터를 내리는 부분입니다.

int move_cluster(int x, int y){
    int cnt = 0;
    for(int i = x+1; i <= N; i++){
        if(map[i][y] == 'x'){
            if(check[i][y] == 0) return INF; //이미 아래에 움직일 미네랄이 있음으로 이번은 X
            else return cnt;
        }
        else cnt++;
    }
    return cnt;
}

vector에 저장된 미네랄 위치를 전부 넣어줍니다.

해당 위치에서 떨어지는 것임으로 for 문은 x+1 ~ N까지 반복해주면 됩니다.

내려가는 도중에, 다른 미네랄을 만나는 경우가 있을 것입니다.

이때, check 배열의 값을 통해서 나눌 수 있습니다.

1. check 배열의 값이 0이다.

-> 공중에 떠 있는 미네랄입니다. 자신보다 아래에 있는 미네랄임으로 자신의 값은 필요없어지게 됩니다.

2. check 배열의 값이 1이다.

-> 바닥에 있는 미네랄을 만났으니, 떨어진 값을 return 해줍니다.

 

함수가 return 될 때마다, cnt의 값을 계속 비교해, 가장 작은 값을 가져오면 됩니다.

 

 

이 3가지 과정을 반복하면 문제가 풀립니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N, M;
char map[101][101];
int check[101][101];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int K;
vector<int> Throw;
vector<P> Move; 

void reset_all(){
    memset(check, 0, sizeof(check));
    Move.clear();
}

void break_mineral(int x, int dir){
    if(dir % 2 == 0){
        int y = 1;
        while(1){
            if(y > M) break;
            if(map[N-x+1][y] == 'x'){
                map[N-x+1][y] = '.';
                break;
            }
            y++;
        }
    }
    else{
        int y = M;
        while(1){
            if(y < 1) break;
            if(map[N-x+1][y] == 'x'){
                map[N-x+1][y] = '.';
                break;
            }
            y--;
        }
    }
}

void bfs(int X, int Y){
    queue<P> q;
    q.push({X, Y});
    check[X][Y] = 1;
    while(!q.empty()){
        int x = q.front().F;
        int y = q.front().S;
        q.pop();
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                if(check[xx][yy] == 0 && map[xx][yy] == 'x'){
                    check[xx][yy] = 1;
                    q.push({xx, yy});
                }
            }
        }
    }
}

int move_cluster(int x, int y){
    int cnt = 0;
    for(int i = x+1; i <= N; i++){
        if(map[i][y] == 'x'){
            if(check[i][y] == 0) return INF; //이미 아래에 움직일 미네랄이 있음으로 이번은 X
            else return cnt;
        }
        else cnt++;
    }
    return cnt;
}

void remake_map(){
    int down = INF;
    for(int i = 0; i < Move.size(); i++){
        int cnt = move_cluster(Move[i].F, Move[i].S);
        if(cnt == INF) continue;
        else down = min(cnt, down);
    }
    if(down == INF) return;
    for(int i = 0; i < Move.size(); i++){
        int x = Move[i].F, y = Move[i].S;
        map[x][y] = '.';
    }
    for(int i = 0; i < Move.size(); i++){
        int x = Move[i].F, y = Move[i].S;
        map[x+down][y] = 'x';
    }
}

bool find_float_cluster(){
    bool can = false; // 공중에 떠있는 미네랄이 없는 경우, false를 return 해준다.
    for(int i = 1; i <= M; i++){
        if(check[N][i] == 0 && map[N][i] == 'x') bfs(N, i);
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(map[i][j] == 'x' && check[i][j] == 0){ // 공중에 떠있는 미네랄
                Move.push_back({i,j}); // 움직이기 위해 좌표를 저장한다.
                can = true;
            }
        }
    }
    return can;
}

void show_map(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cout << map[i][j];
        }
        cout << "\n";
    }
    cout << "\n";
}

void solve(){
    for(int i = 0; i < Throw.size(); i++){
        reset_all();
        break_mineral(Throw[i], i);
        if(!find_float_cluster()) continue; 
        remake_map();
    }
    show_map();
}


int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
        }
    }
    cin >> K;
    for(int i = 1; i <= K; i++){
        int x;
        cin >> x;
        Throw.push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요