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

문제

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

2933번: 미네랄

 

풀이 과정

1. 문제 조건에 맞게 입력을 받는다.

2. 순서대로 발사하여 미네랄을 부순다.

3. 부순 미네랄을 기준으로 주변을 탐색하여 미네랄 군집(cluster)을 파악하고, 중력에 의한 이동을 수행한다.

4. 최종 형태를 출력한다.

 

 

세부 풀이

(1)

초기 형태와 이후 던질 막대의 높이에 대한 정보도 한 번에 입력받아 order 배열에 넣어 저장한 뒤 사용했다.

 

(2) shoot 함수

order 배열에 저장되어 있는 순서대로 입력하며 좌, 우 순서에 맞게 수행한다.

왼쪽에서 날아왔다면 오른쪽, 위, 아래 블록을 시작으로 하는 클러스터를 찾고, 중력에 의한 이동을 수행한다. (날아온 방향은 반드시 빈칸)

오른쪽에서 날아왔다면 왼쪽, 위, 아래 블록을 시작으로 하는 경우에 대한 이동을 수행해야 한다.

 

(3) find_cluster 함수

입력받은 인자 x, y를 기준으로 DFS를 통해 인접해있는 하나의 cluster를 찾은 뒤, 1층 칸이 포함되어 있는지 확인한다.

만약 1층 칸이 cluster에 포함되어 있다면 더 이상 아래로 내려갈 수 없으므로 1층 칸이 포함되어 있다면 어떤 경우라도 이동하지 않는다.

따라서 1층 칸에 도달한다면 flag를 true로 변경하고 바로 DFS를 종료한다.

 

1층 칸이 cluster에 없다면 아래 과정을 수행한다. (Line 91~104)

 - 이동할 칸의 다음 위치가 범위를 벗어나거나 (0 이하) 이동할 칸의 다음 위치에 미네랄이 존재한다면 (map [next_h][y] == 'x') 종료한다.

 - 그렇지 않다면 이동할 칸의 수를 증가시킨다.

 

최종적으로 얻은 md(move_distance) 값과 cluster 벡터에 저장한 위치 정보를 이용하여 map을 수정한다.

 

(4) solve 함수

shoot 함수를 order에 저장되어있는 순서대로 수행한 후, 결과를 출력한다.

 

 

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int r,c,n;
const int max_rcn = 101;

char map[max_rcn][max_rcn];
bool visited[max_rcn][max_rcn];
bool flag;

int order[max_rcn];
vector<pair<int,int>> cluster;

int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

void print_map(){
    for(int i=r;i>=1;i--){
        for(int j=1;j<=c;j++){
            cout << map[i][j];
        }
        cout << '\n';
    }

    return;
}

void Input(){
    cin >> r >> c;
    for(int i=r;i>=1;i--){
        for(int j=1;j<=c;j++){
            cin >> map[i][j];
        }
    }

    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> order[i];
    }

    return;
}


void DFS(int x, int y){
    if(x == 1) {
        flag = true;
        return;
    }

    for(int i=0;i<4;i++){
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if(nx<1 || nx>r || ny<1 || ny>c || visited[nx][ny]) continue;
        if(map[nx][ny]=='.') continue;
        visited[nx][ny] = true;
        cluster.push_back({nx,ny});
        DFS(nx,ny);
    }
}

void find_cluster(int x, int y){
    if(x<1 || y<1 || x>r || y>c) return;
    if(map[x][y]=='.') return;

    //초기화 (모든 좌표 기록을 벡터)
    cluster.clear();
    flag = false;
    memset(visited, false, sizeof(visited));

    cluster.push_back({x,y});
    visited[x][y]= true;
    DFS(x,y);

    //바닥과 붙어있는 클러스터라면 이동하지 않는다.
    if(flag) return;

    //이동이 필요한 경우
    int size = cluster.size();
    //이동 전 위치 '.' 으로 변경
    for(int i=0;i<size;i++){
        int x = cluster[i].first;
        int y = cluster[i].second;
        map[x][y] = '.';
    }
    
    int md = 0; //move_distance
    bool next_md=true;
    while(next_md){
        for(int i=0;i<size;i++){
            int x = cluster[i].first;
            int y = cluster[i].second;
            int next_h = x-md-1;
            if(next_h <=0 || map[next_h][y]=='x') {
                next_md = false;
            }
        }

        if(next_md) md ++;
    }
    
    for(int i=0;i<size;i++){
        int x = cluster[i].first;
        int y = cluster[i].second;
        map[x-md][y] = 'x';
    }
    return;
}


void shoot(int r, int left_right){
    int point;
    if(left_right % 2 == 1){
        for(int i=1;i<=c;i++){
            if(map[r][i]=='x'){
                point = i;
                map[r][i] = '.';
                break;
            }
        }
        //왼쪽에서 날아와서 부딪혔다 -> 오른쪽, 위, 아래 확인
        find_cluster(r,point+1);
        find_cluster(r+1,point);
        find_cluster(r-1,point);
    }
    else{
        for(int i=c;i>=1;i--){
            if(map[r][i]=='x'){
                point = i;
                map[r][i] = '.';
                break;
            }
        }
        //오른쪽에서 날아와서 부딪혔다 -> 왼쪽, 위, 아래 확인
        find_cluster(r,point-1);
        find_cluster(r+1,point);
        find_cluster(r-1,point);
    }
    return;
}

void solve(){
    for(int i=1;i<=n;i++){
        shoot(order[i],i);
    }
    print_map();
}


int main(){
    Input();
    solve();
    return 0;
}

 

결과 및 후기

초기 구현시 군집 탐색을 BFS로 진행했었다. 이때 사용한 queue에서 메모리 초과가 발생했다. 필자는 따로 visited 배열을 사용하지 않고, 다음의 map위치가 'x' 이면 queue에 넣는 식으로 구현했다. 이때 queue에서 꺼낸 칸을 다시 방문하지 않도록, 꺼낸 칸은 '.' 로 변경하는 방법을 통해 반복을 막았었다. 하지만 그렇게 구현하더라도 메모리 초과 오류가 발생했다. 이전 문제인 백조의 호수에서도 겪었던 것 처럼 계속 메모리 초과가 발생했다.

 

/* 
 * baekjoon 2933
 * 
 * 미네랄
 * 
 * https://www.acmicpc.net/problem/2933
 * 
 * 메모리 초과가 발생하는 코드이다.
 * 
 */

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

using namespace std;
int r,c,n;
const int max_rcn = 101;
char map[max_rcn][max_rcn];
int order[max_rcn];
queue<pair<int,int>> q;

int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

void print_map(){
    for(int i=r;i>=1;i--){
        for(int j=1;j<=c;j++){
            cout << map[i][j];
        }
        cout << '\n';
    }

    return;
}

void Input(){
    cin >> r >> c;
    for(int i=r;i>=1;i--){
        for(int j=1;j<=c;j++){
            cin >> map[i][j];
        }
    }

    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> order[i];
    }

    return;
}


void find_cluster(int x, int y){
    if(x<1 || y<1 || x>r || y>c) return;
    if(map[x][y]=='.') return;

    //cluster 가 떨어질 것인가
    bool flag=true;

    //q 초기화 (모든 좌표 기록을 위한 queue)
    while(!q.empty())   q.pop();

    //temp q 생성 (bfs를 위한 queue)
    queue<pair<int,int>> temp;

    //아래 과정이 수행되면 q에는 bfs로 탐색한 좌표들이 저장 되어있다.
    q.push({x,y});
    temp.push({x,y});
    while(!temp.empty()){
        int px = temp.front().first;
        int py = temp.front().second;
        map[px][py] = '.';
        temp.pop();

        for(int i=0;i<4;i++){
            int nx = px + dir[i][0];
            int ny = py + dir[i][1];
            if(nx<1 || ny<1 || nx>r || ny>c) continue;
            if(map[nx][ny]=='.') continue;

            if(nx == 1) flag = false;
            temp.push({nx,ny});
            q.push({nx,ny});
        }
    }


    int size = q.size();
    //이동이 필요 없는 경우 원래 map으로 돌린 뒤 종료
    if(flag == false) {
        for(int i=0;i<size;i++){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            map[x][y] = 'x';
        }
        return;
    }

    //이동이 필요한 경우
    int md = 0; //move_distance
    bool next_md=true;
    while(next_md){
        for(int i=0;i<size;i++){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            int next_h = x-md-1;
            if(next_h <=0 || map[next_h][y]=='x') {
                next_md = false;
            }
            q.push({x,y});
        }

        if(next_md) md ++;
    }

    for(int i=0;i<size;i++){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        map[x-md][y] = 'x';
    }

    return;
}


void shoot(int r, int left_right){
    int point;
    if(left_right % 2 == 1){
        for(int i=1;i<=c;i++){
            if(map[r][i]=='x'){
                point = i;
                map[r][i] = '.';
                break;
            }
        }
        //왼쪽에서 날아와서 부딪혔다 -> 오른쪽, 위, 아래 확인
        find_cluster(r,point+1);
        find_cluster(r+1,point);
        find_cluster(r-1,point);
    }
    else{
        for(int i=c;i>=1;i--){
            if(map[r][i]=='x'){
                point = i;
                map[r][i] = '.';
                break;
            }
        }
        //오른쪽에서 날아와서 부딪혔다 -> 왼쪽, 위, 아래 확인
        find_cluster(r,point-1);
        find_cluster(r+1,point);
        find_cluster(r-1,point);
    }
    return;
}

void solve(){
    for(int i=1;i<=n;i++){
        shoot(order[i],i);
    }
    print_map();
}


int main(){
    Input();
    solve();
    return 0;
}

 

따라서 queue를 사용하는 BFS대신 DFS를 이용하기로 결정했다. 구데타마 님의 꾸준함 블로그의 포스팅을 참고하여 DFS를 적용했다. 

반례를 참고하여 이동 과정에 대한 예외를 고려할 수 있었다. [반례 모음 참고]