[백준] 20058번 마법사 상어와 파이어스톰 (C++)

[문제]

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

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

 

 

[설명]

- 회전시키는 방법을, 회전의 중심을 정한뒤 상 -> 우, 우-> 하 이런식으로 인덱스를 이용해 queue -> temp배열에 넣은뒤, 다시 board로 옮겨주는 방식을 선택했다. 인덱스가 헷갈려서 몇번이나 헤메고 시간도 오래 걸렸다. 

 

-회전 중심에서 끝 행 까지 차근 차근 옮겨주는 방식을 사용했는데, 다른 풀이도 확인해봐야겠다...

 

[코드]

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int N, Q;
int L;

int board[65][65];
vector <pair<int,int>> center;
queue <int> q;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool vis[65][65];
int mx;

void turning(int L){
    center.clear();
    if(L == 0) return;
    for(int i = 0; i < 1 << (N-L); i++){
        for(int j = 0; j < 1 << (N-L); j++){
            center.push_back({(1<<(L - 1))- 1 + i * (1<<L), (1<<(L - 1))- 1 + j * (1<<L)});
        }
    }

    int temp[65][65];
    for (int i = 0; i < center.size(); ++i) { //전체격자
        int cx = center[i].X;
        int cy = center[i].Y;
        for (int j = 0; j < 1<<(L-1); ++j) {//center로 부터 떨어진 거리
            for (int k = cy - j; k <= cy + 1 + j; ++k) { //상 -> 우
                  q.push(board[cx-j][k]);
            }
            for (int k = cx - j; k <= cx + 1 + j; ++k) {
                temp[k][cy+j+1] = q.front();
                q.pop();
            }
        }
        for (int j = 0; j < 1<<(L-1); ++j) {//center로 부터 떨어진 거리
            for (int k = cy - j; k <= cy + 1 + j; ++k) { //하 -> 좌
                q.push(board[cx+1+j][k]);
            }
            for (int k = cx - j; k <= cx + 1 + j; ++k) {
                temp[k][cy-j] = q.front();
                q.pop();
            }
        }
        for (int j = 0; j < 1<<(L-1); ++j) {//center로 부터 떨어진 거리
            for (int k = cx - j; k <= cx + 1 + j; ++k) { //좌-> 상
                q.push(board[k][cy-j]);
            }
            for (int k =  cy + 1 + j; k >= cy - j; --k) {
                temp[cx-j][k] = q.front();
                q.pop();
            }
        }
        for (int j = 0; j < 1<<(L-1); ++j) {//center로 부터 떨어진 거리
            for (int k = cx - j; k <= cx + 1 + j; ++k) { //우->하
                q.push(board[k][cy+1+j]);
            }
            for (int k =  cy + 1 + j; k >= cy - j; --k) {
                temp[cx+1+j][k] = q.front();
                q.pop();
            }
        }
    }

    for(int i = 0; i < 1 << N; i++){
        for (int j = 0; j < 1 << N; ++j) {
            board[i][j] = temp[i][j];
        }
    }


}

void melt(){
    bool melt[65][65] = {false}; //이번턴에 녹았는지 확인
    for(int i = 0; i < 1 << N; i++){
        for (int j = 0; j < 1 << N; ++j) {
            int count = 0;
            if(board[i][j] == 0) continue;
            for (int k = 0; k < 4; ++k) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if(nx < 0|| nx >= 1<<N || ny < 0 || ny >= 1<<N) continue;
                if(board[nx][ny] == 0 && !melt[nx][ny]) continue;
                count++;
            }
            if(count < 3) {
                board[i][j]--;
                melt[i][j] = 1;
            }
        }
    }
}



void BFS(int x, int y){
    queue <pair<int, int>> bq;
    int count = 0;
    vis[x][y] = 1;
    bq.push({x,y});

    while(!bq.empty()){
        pair <int, int> cur = bq.front();
        count ++;
        bq.pop();

        for(int i =0; i < 4; i++)
        {
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if(nx < 0|| nx >= (1<<N) || ny < 0 || ny >= (1<<N)) continue;
            if(board[nx][ny] <= 0) continue;
            if(vis[nx][ny]) continue;
            bq.push({nx,ny});
            vis[nx][ny] = 1;
        }
    }

    mx = max(count, mx);
}

int main(){
    cin >> N >> Q;
    for(int i = 0; i < 1 << N; i++){
        for (int j = 0; j < 1 << N; ++j) {
            cin >> board[i][j];
        }
    }
    for(int i = 0; i < Q; i++){
        cin >> L;
        turning(L);
        melt();
    }


    int sum = 0;
    for(int i = 0; i < 1 << N; i++){
        for (int j = 0; j < 1 << N; ++j) {
            sum+= board[i][j];
            if(!vis[i][j] && board[i][j]!=0) BFS(i,j);
        }
    }

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


}

- 몇가지 실수 들이 많아서 다시 되돌아가는 경우가 많았는데 잔실수를 줄이는 게 좋을듯