[ 백준 20058 ] 마법사 상어와 파이어스톰 (C++) - 구현, 시뮬레이션

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 회전을 시켜야 하는데, 이는 2^N 이다.
2. N<=6 이므로 최대 한 변의 길이는 64이므로 한줄씩 옮겨줄 temp[64]를 만들어 준다.
3. rotate 함수에서 시계 방향으로 돌릴 수 있게 해준다. 단, 가장 바깥 쪽 부터 한 바퀴씩 돌리는 방식으로 하였다. 이 때, 동서남북으로 설명하자면, 북을 저장하고 서->북, 남->서, 동->남, 저장된 북->동 순서로 돌렸다.
4. rotate 하는 함수는 L에 영향을 받는데, 이는 매개 변수 size로 넣어주었다.
5. rotate는 왼쪽 위, 오른쪽 아래 2개의 x,y rotate해야 되는 정사각형의 변을 표현하였다.
6. 그 다음은 녹이는 것과 bfs인데, 굳이 설명해놓지 않겠다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;

int N, Q;
int MAP[64][64];
bool visit[64][64];
int temp[64];
int next_x[] = { 1,-1,0,0 };
int next_y[] = { 0,0,1,-1 };
vector<int> Ls;
queue<pair<int, int>> q;

void init() {
    cin >> N >> Q;
    for (int y = 0; y < pow(2, N); y++) {
        for (int x = 0; x < pow(2, N); x++) {
            cin >> MAP[y][x];
        }
    }
    for (int i = 0; i < Q; i++) {
        int L; cin >> L;
        Ls.push_back(L);
    }
}

void rotate(int sx, int sy, int size) {
    if (size == 0) return;

    int ex = sx + size - 1, ey = sy + size - 1;
    int index = 0;
    for (int i = sx; i < sx + size - 1; i++) temp[index++] = MAP[sy][i]; // N 복사
    for (int i = sx; i < sx + size - 1; i++) MAP[sy][i] = MAP[ey--][sx]; // W => N
    ey = sy + size - 1;
    for (int i = ey; i > ey - size + 1; i--) MAP[i][sx] = MAP[ey][ex--]; // S => W
    ex = sx + size - 1;
    for (int i = sy; i < sy + size - 1; i++) MAP[ey][ex--] = MAP[i][sx + size - 1]; // E => S
    ex = sx + size - 1;
    index = 0;
    for (int i = sy; i < sy + size - 1; i++) MAP[i][ex] = temp[index++]; // N복사 => E

    rotate(sx + 1, sy + 1, size - 2);
} 

bool melt(int x, int y, int size) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int nx = x + next_x[i];
        int ny = y + next_y[i];
        if (nx > -1 && ny > -1 && nx < size && ny < size) {
            if (MAP[ny][nx] > 0) cnt++;
        }
    }
    if (cnt < 3) return true;
    return false;
}

void fire(int size) {
    for (int y = 0; y < size; y++) {
        for (int x = 0; x < size; x++) {
            if (MAP[y][x] == 0) continue;
            else if (x == 0 && y == 0) continue;
            else if (x == 0 && y == size - 1) continue;
            else if (x == size - 1 && y == 0) continue;
            else if (x == size - 1 && y == size - 1) continue;
            if (melt(x, y, size)) q.push({ x,y });
        }
    }
    while (!q.empty()) {
        int X = q.front().first, Y = q.front().second;
        MAP[Y][X]--;
        q.pop();
    }
    if (MAP[0][0] > 0)MAP[0][0]--;
    if (MAP[size - 1][0] > 0)MAP[size - 1][0]--;
    if (MAP[0][size - 1] > 0)MAP[0][size - 1]--;
    if (MAP[size - 1][size - 1] > 0)MAP[size - 1][size - 1]--;
}

int bfs(int x, int y) {
    int Size = 0;

    q.push({ x,y });
    visit[y][x] = true;
    while (!q.empty()) {
        int cur_x = q.front().first, cur_y = q.front().second;
        q.pop();
        Size++;
        for (int i = 0; i < 4; i++) {
            int nx = cur_x + next_x[i], ny = cur_y + next_y[i];
            if (nx > -1 && ny > -1 && nx < pow(2, N) && ny < pow(2, N)) {
                if (!visit[ny][nx] && MAP[ny][nx] > 0) {
                    q.push({ nx,ny });
                    visit[ny][nx] = true;
                }
            }
        }
    }

    return Size;
}

int main() {

    init();

    for (int i = 0; i < Q; i++) {
        int size = pow(2, Ls[i]);
        for (int y = 0; y < pow(2, N); y+=pow(2,Ls[i])) {
            if (size == 1) break;
            for (int x = 0; x < pow(2, N); x+=pow(2,Ls[i])) {
                rotate(x, y, size);
            }
        }
        fire(pow(2, N));
    }

    int answer = 0;
    int Size = 0;
    for (int y = 0; y < pow(2, N); y++) {
        for (int x = 0; x < pow(2, N); x++) {
            answer += MAP[y][x];
            if (!visit[y][x] && MAP[y][x] > 0) Size = max(Size, bfs(x, y));
        }
    }

    cout << answer << endl << Size;

    return 0;
}

---

🤔 문제 후기

문제 자체가 어렵진 않았고, rotate하는 방식도 생각하는데, 어렵진 않았는데, 구현할 때, 실수하는 부분이 많았다. 특히 sx,sy,ex,ey를 사용하고, 초기화 하는 부분에서 실수하거나 사용하기 전에 Size = size - 1 로 초기화하여 대신 사용했는데, 이 부분에서도 계속해서 실수를 해서 결국에는 매개변수와 sx~ey 로만 구현하니 문제가 해결됐다. 문제 자체가 어렵다고는 생각 안하는데, 실수 없이 구현할려면 시간은 많이 걸리는 문제인 것 같다.