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

www.acmicpc.net/problem/2933

2933번: 미네랄

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    1. 명령어를 for문으로 하나씩 꺼내고, 왼손 또는 오른손에 따라 동작 수행하기

    2. 명령에 따라 막대기 던져서 부수기

    3. 부숴진 후에 공중에 떠있는 미네랄 내리기

        3-1. 바닥에 붙은 미네랄을 1로 표시. BFS이용

        3-2. 바닥에 공중에 떠있는 미네랄은 1로 표시가 안되어 있어야 한다. 2로 표시한다. 그리고 동시에 mat에서 지워주면서, 위치를 vector에 넣주기 

        3-3. 위치가 저장된 vector를 가지고 와서, 한 칸씩 내려보면서 다른 미네랄 또는 바닥에 닿는지 확인하고, 닿으면 mat에 미네랄 기록하기

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
int R, C, N;
 
char mat[101][101];
int isVisited[101][101]; // 미네랄 방문했는지  
vector<int> cmd;
vector<pair<int, int> > broken; // 공중에 뜬 미네랄 담는 용기  
 
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
void print(){
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cout << mat[i][j];
        }
        cout << endl;
    }
}
 
bool isValid(int y, int x){
    return (y>=0 && y<R) && (x>=0 && x<C);
}
 
void BFS(int y, int x, int mark){
    
    broken.clear();
    queue<pair<int, int> > q;
    q.push({y, x});
    
    while(!q.empty()){
        
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        isVisited[y][x] = mark;
        broken.push_back({y, x}); // 공중에 떠있는 미네랄 위치 담기  
        if(mark == 2) mat[y][x] = '.'; // 공중에 떠있는 미네랄은 제거하기  
        
        for(int d=0; d<4; d++){
            int ny = y + dir[d][0];
            int nx = x + dir[d][1];
            
            if(!isValid(ny, nx)) continue;
            if(isVisited[ny][nx]) continue;
            if(mat[ny][nx] != 'x') continue;
            
            isVisited[ny][nx] = mark;
            broken.push_back({ny, nx});
            q.push({ny, nx});
        }
    }    
}
 
 
void arrange_mineral(){
    // 바닥에 연결된 미네랄을 찾아서 표시하기  
    for(int j=0; j<C; j++){
        if(mat[R-1][j] == 'x' && !isVisited[R-1][j]){
            BFS(R-1, j, 1);
        }
    }
    
    // 바닥과 연결이 되지 않은 미네랄 찾기  
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            if(mat[i][j] == 'x' && isVisited[i][j] == 0){
                BFS(i, j, 2);
                break;
            }
        }
    }
    
    // 떠있는 미네랄 내리기
    while(true){
        
        if(broken.size() == 0) break;
        
        vector<pair<int, int> > broken2;
        
        // 떠있는 미네랄을 한 칸씩 내려보면서, 바닥에 닿거나 미네랄에 닿는데 확인  
        for(int i=0; i<broken.size(); i++){
            int ny = broken[i].first +1;
            int nx = broken[i].second;
            
            // 닿으면, 미네랄 옮기기  
            if(isVisited[ny][nx] == 1 || !isValid(ny, nx)){
                for(int j=0; j<broken.size(); j++){
                    mat[broken[j].first][broken[j].second] = 'x';
                }
                return;
            }
             
            broken2.push_back({ny, nx});
        }
        // 모두 한 칸씩 옮기기 성공했으면, 복사하기  
        broken = broken2;
    } 
 
} 
 
 
void solution(){
    
    // -1이면 왼쪽, +1이면 오른쪽에서 던진다. 
    int turn = -1;
    
    for(int i=0; i<cmd.size(); i++){
        memset(isVisited, 0, sizeof(isVisited));
        // 왼쪽 
        if(turn == -1){
            // 막대기를 던져서 미네랄 부수기  
            int y = R - cmd[i];
            int x = 0;
            while(true){
                if(mat[y][x] == 'x') {
                    mat[y][x] = '.';
                    break;
                }
                x += 1;
                if(x >= C) break;
            }
            // 공중에 떠있는 미레랄 내리기  
            arrange_mineral();
        }
        // 오른쪽  
        else {
            int y = R - cmd[i];
            int x = C;
            while(true){
                if(mat[y][x] == 'x') {
                    mat[y][x] = '.';
                    break;
                }
                x -= 1;
                if(x < 0) break;
            }
            arrange_mineral();
        }
        
        turn *= -1;
    }
    
    print();
}
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    cin >> R >> C;
    
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            cin >> mat[i][j];
        }
    }
    
    cin >> N;
    int num;
    for(int i=0; i<N; i++) {
        cin >> num;
        cmd.push_back(num);
    }
    
    solution();
}

 

 

 

시행착오