마법사 상어와 블리자드 (feat. 백준, 21611번)

마법사 상어와 블리자드
https://www.acmicpc.net/problem/21611

21611번: 마법사 상어와 블리자드

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/21611
#include <iostream>
#include <vector>
using namespace std;
int N, M, arr[50][50], tmp[49 * 49 + 1], dx[4], dy[4], rx[4], ry[4], sx, sy;
int explosion_count[3];
inline void casting_blizzard(const int& d, const int& s) {
    auto x = sx, y = sy;
    for (int idx = 0, nx, ny; idx < s; ++idx) {
        nx = x + dx[d - 1], ny = y + dy[d - 1];
        if (1 <= nx && nx <= N && 1 <= ny && ny <= N)
            arr[nx][ny] = 0, x = nx, y = ny;
    }
}
inline void make_arr_to_tmp() {
    auto d = 0, move_length = 1, x = sx, y = sy, index = 0;
    for (auto idx = 0; idx <= N * N; ++idx)
        tmp[idx] = 0;
    while (true) {
        for (int idx = 0, i; idx < 2; ++idx) {
            x = x + rx[d], y = y + ry[d];
            if (x < 1 || x > N || y < 1 || y > N)
                return;
            for (i = 0; i < move_length; ++i) {
                if(arr[x][y] != 0)      tmp[index++] = arr[x][y];
                if(i != (move_length - 1))
                    x = x + rx[d], y = y + ry[d];
            }
            d = (d + 1) % 4;
        }
        ++move_length;
    }
}
inline void make_tmp_to_arr() {
    auto d = 0, move_length = 1, x = sx, y = sy, index = 0;
    for (int ix = 0, iy; ix <= N; ++ix)
        for (iy = 0; iy <= N; ++iy)
            arr[ix][iy] = 0;
    arr[sx][sy] = -1;
    while (true) {
        for (int idx = 0, i; idx < 2; ++idx) {
            x = x + rx[d], y = y + ry[d];
            if (x < 1 || x > N || y < 1 || y > N)
                return;
            for (i = 0; i < move_length; ++i) {
                if (tmp[index] == 0)     return;
                arr[x][y] = tmp[index++];
                if (i != (move_length - 1))
                    x = x + rx[d], y = y + ry[d];
            }
            d = (d + 1) % 4;
        }
        ++move_length;
    }
}
inline void explosion() {
    while (true) {
        bool explosed = false;
        vector<int> store;
        auto value = tmp[0];
        for (auto idx = 0; idx <= N * N; ++idx) {
            if (value == tmp[idx])       store.push_back(idx);
            else {
                if (store.size() >= 4) {
                    for (const auto& i : store)
                        tmp[i] = 0;
                    explosed = true, explosion_count[value - 1] += static_cast<int>(store.size());
                }
                store.clear(), store.push_back(idx), value = tmp[idx];
            }
            if (tmp[idx] == 0)
                break;
        }
        if (!explosed)
            break;

        int tt[49 * 49 + 1] = { 0 }, index = 0;
        for (auto idx = 0; idx <= N * N; ++idx) {
            if (tmp[idx] != 0)       tt[index++] = tmp[idx];
            tmp[idx] = 0;
        }
        for (auto idx = 0; idx <= N * N; ++idx) {
            if (tt[idx] == 0)    break;
            tmp[idx] = tt[idx];
        }
    }
}
inline void make_group() {
    vector<int> store;
    auto index = 0, count = 0, value = tmp[0];
    for (auto idx = 0; idx <= N * N; ++idx) {
        if (value == tmp[idx])       ++count;
        else {
            store.push_back(count), store.push_back(value);
            if (store.size() == (N * N - 1))
                break;
            count = 1, value = tmp[idx];
        }
        if (tmp[idx] == 0)
            break;
    }
    for (auto idx = 0; idx <= N * N; ++idx)
        tmp[idx] = 0;
    for (auto idx = 0; idx < static_cast<int>(store.size()); ++idx)
        tmp[idx] = store[idx];
}
int main() {
    ios::sync_with_stdio(false), cin.tie(), cout.tie();
    dx[0] = -1, dx[1] = 1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = -1, dy[3] = 1;
    rx[0] = rx[2] = 0, rx[1] = 1, rx[3] = -1;
    ry[0] = -1, ry[1] = ry[3] = 0, ry[2] = 1;
    explosion_count[0] = explosion_count[1] = explosion_count[2] = 0;
    cin >> N >> M;
    sx = sy = (N + 1) / 2;          // 상어 위치
    for (int ix = 1, iy; ix <= N; ++ix)
        for (iy = 1; iy <= N; ++iy)
            cin >> arr[ix][iy];
    arr[sx][sy] = -1;
    for (int m = 0, d, s; m < M; ++m) {
        cin >> d >> s;
        casting_blizzard(d, s);
        make_arr_to_tmp();
        explosion();
        make_group();
        make_tmp_to_arr();
    }
    auto result = 0;
    for (auto idx = 0; idx < 3; ++idx)
        result += explosion_count[idx] * (idx + 1);
    cout << result << endl;
    return 0;
}
// *&)*@*

1. 2차원 배열의 중앙부터 반시계 방향으로 회전을 하는 순서를 1차원 배열로 옮긴다고 생각하면, 문제는 굉장히 간단해집니다.
2. 인접한 수가 4개 이상일때 폭발하는 것은, 1차원 배열에서 연속된 동일값 4개 이상을 0으로 채우면 되고, 만약 폭발되었다면 0을 제거한 후 폭발이 일어나지 않을때까지 반복하면 됩니다.
3. 인접한 동일 숫자에 대한 그룹핑 (1이 2개, 2가 1개, 3이 2개 면 배열 순서상 2 1 1 2 2 3 이 됩니다.) 또한 1차원 배열에서 생각하면 간단합니다.
4. 그룹핑을 할때 함정이 있습니다. (여기서 3시간은 날린듯 합니다.) 바로 구슬이 칸의 수보다 많아지면 버려야 한다는 겁니다. 즉, 3X3짜리 행렬안에는 중앙을 제외한 총 8칸만 숫자가 들어가야 하므로, 1차원 배열 또한 8개로 제한해야 합니다.