[C++] BOJ 2933번: 미네랄

문제

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

 

입력 1

5 6
. . . . . .
. . X X . .
. . X . . .
. X X X X .
1
3

출력 1

. . . . . .
. . . . . .
. . X X . .
. . X X . .
. X X X X .

코드

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define y first
#define x second
using namespace std;

//2933번 미네랄

//2차원 배열 선언
char arr[101][101];
int visited[101][101];      //dfs를 위한 방문 배열
int R, C;
vector<pair<int,int>> cluster;
int arrow[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

void DFS(int yIdx, int xIdx) {
    if (arr[yIdx][xIdx] == '.' || visited[yIdx][xIdx]) return;
    visited[yIdx][xIdx] = true;
    cluster.push_back({yIdx,xIdx});
    //좌우위아래 탐색
    for (int i = 0; i < 4; i++) {
        int ny = yIdx + arrow[i][0];
        int nx = xIdx + arrow[i][1];    
        if (nx >= 0 && nx < C && ny >= 0 && ny < R)
            DFS(ny, nx);
    }
}

void checkCluster() {
    memset(visited, 0, sizeof(visited));
    for (int a = 0; a < R; a++) {
        for (int b = 0; b < C; b++) {
            if (arr[a][b] == '.' || visited[a][b]) continue;
            cluster.clear();
            DFS(a,b);
            vector<int> low(C, -1);     //vector(컨테이너 크기, 각각 할당될 값)
            for (int z = 0; z < cluster.size(); z++) {
                pair<int, int> p= cluster[z];
                low[p.x] = max(low[p.x], p.y);
                arr[p.y][p.x] = '.';
            }

            //얼마나 밑으로 옮길지 i에 넣기
            int lowmove = R;
            for (int i, j = 0; j < C; j++) {
                if (low[j] == -1) continue;
                i = low[j];

                //'.'이 아닌경우, 탐색 높이가 높이보다 작은 경우
                while (i < R &&arr[i][j] == '.') {
                    i++;
                }
                lowmove = min(lowmove, i - low[j] - 1);
            }

            for (int i = 0; i < cluster.size(); i++) {
                pair<int, int> p = cluster[i];
                p.y += lowmove;
                arr[p.y][p.x] = 'x';
                visited[p.y][p.x] = true;
            }
        }
    }
    
}

void shoot(int orderNum,int height) {
    //왼쪽인지 오른쪽인지 판단
    height = R - height;
    if (orderNum % 2 == 0) {
        for (int i = 0; i < C; i++) {
            if (arr[height][i] == 'x') {
                arr[height][i] = '.';
                break;
            }
        }
    }
    else {
        for (int i = C-1; i >= 0; i--) {
            if (arr[height][i] == 'x') {
                arr[height][i] = '.';
                break;
            }
        }
    }
    
    checkCluster();
}

int main() {
    
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);


    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
        }
    }
    int N,height=0;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> height;
        shoot(i, height);
    }

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

    return 0;
}

*간단한 해설*

checkCluster() 함수 부분은 https://100100e.tistory.com/152 이 블로그 분의 글을 참고하여서 제작하였다. 제일 나랑 생각이 비슷하기도 했고 알기 쉽게 작성되어있어서 좋았다. checkCluster() 부분을 자세하게 설명해볼까 싶다.

 memset(visited, 0, sizeof(visited));
    for (int a = 0; a < R; a++) {
        for (int b = 0; b < C; b++) {

 

checkCluster는 부메랑을 던진 후에 떨어지는 클러스터들을 판단하기 위한 함수로써 실행된다. 따라서 DFS를 다시 사용하려면 visited 배열을 초기화 시켜줘야한다. 그를 위해 memset 함수를 이용하였다. 나머지 for문은 R x C 크기의 맵을 for문을 통해 돌린다.

if (arr[a][b] == '.' || visited[a][b]) continue;
cluster.clear();
DFS(a,b);

그 다음에는 해당 맵의 칸이 . 으로 비어있는 칸이거나 이미 방문한 배열일 경우 그대로 밑의 계산을 하지 않고 넘어간다. 그렇지 않은 경우 DFS 함수를 통해서 해당 클러스터를 기준으로 좌우위아래를 탐색해서 cluster 벡터에 넣는다.

vector<int> low(C, -1);     //vector(컨테이너 크기, 각각 할당될 값)
for (int z = 0; z < cluster.size(); z++) {
    pair<int, int> p= cluster[z];
    low[p.x] = max(low[p.x], p.y);
    arr[p.y][p.x] = '.';
}

그 후에  low 라는 땅에 가장 가까운 클러스터를 저장하는 벡터 배열을 선언한다. low(C,-1) 이렇게 선언하면 C 크기 만큼을 -1의 값으로 할당한다는 말이다. 그 다음 for문을 통해서 저장된 cluster만큼 돌려주고 만약 해당 클러스터의 높이 값인 p.y 값이 만약에 기존에 저장된 높이 값인 low[p.x]와 비교했을 때 큰 값을 low[p.x]에 저장해준다. 저장한 다음에는 해당 값은 나중에 다시 떨어진 클러스터 값으로 변경해줄 것임으로 미리 .으로 변경 시켜준다.

int lowmove = R;
for (int i, j = 0; j < C; j++) {
    if (low[j] == -1) continue;
    i = low[j];

    //'.'이 아닌경우, 탐색 높이가 높이보다 작은 경우
    while (i < R &&arr[i][j] == '.') {
        i++;
    }
    lowmove = min(lowmove, i - low[j] - 1);
}

얼만큼 밑으로 옮길지 계산하는 부분이다. lowmove 변수에는 가장 많이 내려갈 수 있는 값 높이 R값을 넣은 다음 비교해가면서 작으면 변경하는 형식이다. if(low[j]==-1) continue; 의 경우 땅에 가장 가까운 클러스터가 없는 경우에는 연산을 하지 않고 넘어간다. 그렇지 않을 경우 i = low[j];로 땅에 가장 가까운 클러스터의 높이를 넣는다. 그 후 while문을 통해서 만약 해당 좌표의 클러스터가 빈공간인 경우 내려가야할 칸의 값인 i를 ++해준다. 해당 while문이 긑나고 나면 min 함수를 통해 기존의 lowmove 값과 i-low[j]-1을 비교한다. arr[i][j]의 경우 아까 위에서 .으로 만들어놓았기 때문에 한개가 더 세어진다. 따라서 내려가야할 칸의 수 i 에서 -1을 한 다음 기존 높이인 low[j]를 빼주면 내려가야할 칸의 갯수가 나온다.

for (int i = 0; i < cluster.size(); i++) {
                pair<int, int> p = cluster[i];
                p.y += lowmove;
                arr[p.y][p.x] = 'x';
                visited[p.y][p.x] = true;
}

마지막으로 클러스터의 갯수 만큼 for문을 돌려서 lowmove 만큼 모든 클러스터를 옮겨준다.

 

 

 

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*