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

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

2933번: 미네랄

 

나의 첫 골드 1 해금 문제이다. 

문제 이해는 어렵지 않은데 구현하기가 매우 까다롭다. 그리고 DFS와 BFS의 깊은 차이를 느낄 수 있었다. 

 

- 문제 조건

 두명이 번갈아가면서 미네랄을 하나씩 지우고 만약 하늘에 떠 있다면 미네랄이 클러스터 체로 떨어지게 된다. 그리고 미네랄이나 땅에 만날 때 까지 무너지며 클러스터의 형태는 변하지 않는다.

 

- 나의 접근법

 먼저 땅바닥에 붙어있는 미네랄들을 dfs한다. 그리고 0,0부터 돌며 방문하지 않은 미네랄. 즉, 바닥에 붙어 있지 않은 미네랄을 발견하면 이 미네랄 클러스터는 하늘에 떠있는 것이므로 방문하지 않은 클러스터를 모두 바닥 or 미네랄에 붙도록 이동시킨다. 이동시키는 함수를 구현하는 것도 까다로웠다. 

나의 경우엔 y축으로 계속 가다가 바닥 혹은 미네랄을 만날 때 까지 갯수를 세고 클러스터들 중 가장 작은 카운트 만큼 클러스터를 모두 이동시킨다. 그리고 계속 반복한다. 

 

- 올바른 접근법

 결론부터 말하면 위 방법은 틀리지 않았다. 그러나 dfs가 문제였다. dfs는 내 상상이상으로 느렸다.. VS에서도 터져버렸다. 오버헤드 때문일까.. 같은 방법인데 bfs를 사용하니까 맞았다.

이러한 단순 방문체크를 위한 탐색은 bfs를 사용해야함을 깨달은 문제였다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 101
using namespace std;

char kernel[MAX][MAX];
bool check[MAX][MAX] = { false, };
int R, C, N;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void Moving(int cnt) {
    if (cnt == 0)
        return;
    for (int i = R - 1; i > -1; i--) {
        for (int j = 0; j < C; j++) {
            if (!check[i][j] && kernel[i][j] == 'x') {
                kernel[i + cnt][j] = 'x';
                kernel[i][j] = '.';
            }
        }
    }
}

int Move_cnt() {
    int mcnt = 100000;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            bool checking = true;
            if (!check[i][j] && kernel[i][j] == 'x') { // false 이면
                int cnt = 0;
                for (int k = i + 1; k < R; k++) {
                    if (kernel[k][j] == 'x') {
                        if (check[k][j] == false) {
                            checking = false;
                            break;
                        }
                        else {
                            checking = true;
                            break;
                        }
                    }
                    else {
                        cnt++;
                    }
                }
                if (cnt != 0 && checking) {
                    //cout << i << " " << j << endl;

                    mcnt = min(mcnt, cnt);
                }
            }
        }
    }
    if (mcnt == 100000)
        return 0;
    return mcnt;
}

void init() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            check[i][j] = false;
        }
    }
}

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    check[x][y] = true;

    q.push({ x,y });
    
    while (!q.empty()) {
        int nx = q.front().first;
        int ny = q.front().second;
        q.pop();
    
        for (int i = 0; i < 4; i++) {
            int nextx = nx + dx[i];
            int nexty = ny + dy[i];

            if (nextx >= 0 && nexty >= 0 && nextx < R && nexty < C)
            {
                if (kernel[nextx][nexty] == 'x' && check[nextx][nexty] == false)
                {
                    check[nextx][nexty] = true;
                    q.push(make_pair(nextx, nexty));
                }
            }
        }
    }
}

void solution(int stick, bool ch) {
    int row = R - stick;
    if (ch) { // 왼쪽에서 어택
        for (int i = 0; i < C; i++) {
            if (kernel[row][i] == 'x') {
                kernel[row][i] = '.';
                break;
            }
        }
    }
    else {
        for (int i = C - 1; i > -1; i--) {
            if (kernel[row][i] == 'x') {
                kernel[row][i] = '.';
                break;
            }
        }
    }
   
    for (int i = C - 1; i > -1; i--) {
        if(check[R - 1][i] == false && kernel[R - 1][i] == 'x')
            bfs(R - 1, i);
    }

    int mov = Move_cnt();

    Moving(mov);
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cin >> R >> C;

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

    cin >> N;

    int stick;
    for (int i = 0; i < N; i++) {
        cin >> stick;
        init();
        if (i % 2 == 0) {
            solution(stick, true);
        }
        else {
            solution(stick, false);
        }
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << kernel[i][j];
        }
        cout << '\n';
    }
}