[BOJ 20058] 마법사 상어와 파이어스톰

20058번: 마법사 상어와 파이어스톰

1. 문제 설명

 

2. 구현 아이디어 1 - 맞았습니다!!

크게 3가지를 구현해야 한다.

1. 모든 부분 격자를 시계 방향으로 90도 회전시킨다.
2. 모든 칸을 순회하며 인접한 4칸 중 3칸 이상 얼음이 있지 않은 칸은 얼음의 양을 1 줄인다.
3. 남아있는 얼음의 합과 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구한다.

 

부분 격자 회전

이 부분은 혼자 떠올리기 어려워 다른 사람의 풀이를 참고하였다.

 

부분 격자이므로 회전시킬 배열의 시작 좌표가 (0, 0)이 아니라 (y, x)부터 시작한다.

부분 격자의 한 변의 길이는 L이므로 반복문에서 x++, y++이 아닌 x+=L, y+=L이 된다.

 

현재 격자(board)의 N번째 열을 다음 격자(temp)의 N번째 행으로 바꾸어야 한다.

그러므로 행에 대한 인덱스 b가 y값과 함께 사용되고, 열에 대한 인덱스 a가 x값과 함께 사용되는 것이다.

int L = pow(2, l);
vector<vector<int>> temp = vector<vector<int>>(N, vector<int>(N, 0));
for (int y = 0; y < N; y += L) { // 격자 시작 좌표 y 값
    for (int x = 0; x < N; x += L) { // 격자 시작 좌표 x 값
        for (int a = 0; a < L; ++a) { // 열 인덱스
            for (int b = 0; b < L; ++b) { // 행 인덱스
                temp[y + b][x + L - a - 1] = board[y + a][x + b];
            }
        }
    }
}

board = temp;

 

얼음의 양 줄이기

얼음의 양은 0보다 작아질 수 없다는 점을 주의해야 한다!

 

그리고 모든 칸을 순회하면서 이전 칸에서 줄어든 얼음의 양이 다음 칸에 영향을 주면 안된다. 그러므로 이중 반복문에서 얼음의 양을 줄이면 안된다. 이중 반복문을 순회하며 meltings 벡터에 얼음의 양을 줄일 좌표들을 저장하고, 반복문을 마친 뒤 meltings 함수를 순회하며 해당 좌표에 있는 얼음의 양을 1 줄여주었다.

vector<pair<int, int>> meltings;
for (int j = 0; j < N; ++j) {
    for (int k = 0; k < N; ++k) {
        // 인접한 칸 중 얼음이 있는 칸을 센다
        int cnt = 0;
        for (int m = 0; m < 4; ++m) {
            int nx = j + dx[m];
            int ny = k + dy[m];

            // index out of range
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

            if (board[nx][ny] > 0) cnt ++;
        }

        // 그 칸이 3보다 작다면 얼음의 양이 1 줄어든다
        // 얼음의 양은 0보다 작을 수 없다
        if (cnt < 3 && board[j][k] > 0) meltings.push_back({j, k});
    }
}
for (auto melting : meltings) {
    board[melting.first][melting.second]--;
}
}

남아있는 얼음의 합과 가장 큰 덩어리가 차지하는 칸의 개수 구하기

BFS를 사용하여 구현하였다.

처음에는 group(덩어리가 차지하는 칸의 개수)를 1 더하는 코드를 (nx, ny)를 큐에 삽입하는 코드 아래에 작성하였다. 하지만, 이렇게 할 경우 이미 센 칸을 또 셀 수 있으므로 큐에서 (cx, cy)를 제거하는 코드 아래로 이동시켰다.

int mx = 0;
vector<vector<bool>> visited = vector<vector<bool>>(N, vector<bool>(N, false));
for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        sum += board[i][j];
        if (board[i][j] == 0) continue;

        queue<pair<int, int>> qq;
        int group = 0;

        if (!visited[i][j]) {
            qq.push({i, j});
            visited[i][j] = true;

            while (!qq.empty()) {
                int cx = qq.front().first;
                int cy = qq.front().second;

                group++;
                qq.pop();

                for (int k = 0; k < 4; ++k) {
                    int nx = cx + dx[k];
                    int ny = cy + dy[k];

                    if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                    if (board[nx][ny] == 0) continue;
                    if (visited[nx][ny]) continue;

                    qq.push({nx, ny});
                    visited[nx][ny] = true;
                }
            }

            if (group > mx) mx = group;
        }
    }
}

 

전체 코드

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

using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

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

    int n, q; // 격자 칸, 단계 수
    cin >> n >> q;

    int N = pow(2, n);
    int sum = 0; // 남아있는 얼음의 합
    vector<vector<int>> board = vector<vector<int>>(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> board[i][j];
        }
    }

    vector<int> levels = vector<int>(q, 0);
    for (int i = 0; i < q; ++i) {
        cin >> levels[i];
    }

    for (int i = 0; i < q; ++i) {
        int l = levels[i];

        // 격자를 2^l * 2^l의 부분 격자로 나눈다
        // 모든 부분 격자를 90도 회전
        int L = pow(2, l);
        vector<vector<int>> temp = vector<vector<int>>(N, vector<int>(N, 0));
        for (int y = 0; y < N; y += L) {
            for (int x = 0; x < N; x += L) {
                for (int a = 0; a < L; ++a) {
                    for (int b = 0; b < L; ++b) {
                        temp[y + b][x + L - a - 1] = board[y + a][x + b];
                    }
                }
            }
        }

        board = temp;

        // 모든 칸을 순회하며 얼음이 있는 칸이 3개 이상 인접해 있지 않다면 얼음의 양을 1 줄인다
        vector<pair<int, int>> meltings;
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                // 인접한 칸 중 얼음이 있는 칸을 센다
                int cnt = 0;
                for (int m = 0; m < 4; ++m) {
                    int nx = j + dx[m];
                    int ny = k + dy[m];

                    // index out of range
                    if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

                    if (board[nx][ny] > 0) cnt ++;
                }

                // 그 칸이 3보다 작다면 얼음의 양이 1 줄어든다
                // 얼음의 양은 0보다 작을 수 없다
                if (cnt < 3 && board[j][k] > 0) meltings.push_back({j, k});
            }
        }
        for (auto melting : meltings) {
            board[melting.first][melting.second]--;
        }
    }

    // 모든 칸을 순회하며 BFS로 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 센다
    int mx = 0;
    vector<vector<bool>> visited = vector<vector<bool>>(N, vector<bool>(N, false));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            sum += board[i][j];
            if (board[i][j] == 0) continue;

            queue<pair<int, int>> qq;
            int group = 0;

            if (!visited[i][j]) {
                qq.push({i, j});
                visited[i][j] = true;

                while (!qq.empty()) {
                    int cx = qq.front().first;
                    int cy = qq.front().second;

                    group++;
                    qq.pop();

                    for (int k = 0; k < 4; ++k) {
                        int nx = cx + dx[k];
                        int ny = cy + dy[k];

                        if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                        if (board[nx][ny] == 0) continue;
                        if (visited[nx][ny]) continue;

                        qq.push({nx, ny});
                        visited[nx][ny] = true;
                    }
                }

                if (group > mx) mx = group;
            }
        }
    }


    cout << sum << "\n";
    cout << mx << "\n";

    return 0;
}