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

[문제]

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

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

 

[풀이]

 

파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다.

격자별 회전을 처리해주기 위해 rotate api의 인자로 각 격자의 시작 점과 길이를 넘겨주도록 했다.

 

(0,0)을 기준으로 90도 시계 방향 회전하면 (x,y) -> (y, (N-1)-x)로 위치가 변한다.

그런데 해당 문제에서는 격자별로 90도 회전이므로 0부터 len 이전까지 반복하면서 tmp 배열에 (0,0)부터 회전한 값을 저장한다.

tmp[j][len-1-i] = map[x+i][y+j];

그리고 tmp (0,0)부터 (len-1,len-1) 까지 다시 map 배열로 옮겨준다.

map[x+i][y+i] = tmp[i][j];

이와 같은 방식으로 90도 회전을 구현했다.

 

회전 후 melt_ice api를 통해 얼음을 녹여준다.

 

그리고 find_max_lump api에서 남아있는 얼음의 합을 구하고 가장 큰 덩어리가 차지하는 칸의 개수를 출력해줬다. 

 

 

[코드]

 

#include <iostream>
#include <queue>

#define MAX 70

using namespace std;

struct pos {
    int x,y;
};

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

int N,Q,L;
int map[MAX][MAX]={0,};

// 격자 시계방향 회전
void rotate(int x, int y, int len){
    int tmp[MAX][MAX]={0,};

    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            tmp[j][len-1-i]=map[x+i][y+j];
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            map[x+i][y+j]=tmp[i][j];
}

void rotate_grid()
{
    int len = 1 << L;
    
    for(int i=0;i<N;i+=len){
        for(int j=0;j<N;j+=len){
            rotate(i,j,len);
        }
    }
}

void melt_ice()
{
    int tmp[MAX][MAX]={0,};
    
    for(int x=0;x<N;x++){
        for(int y=0;y<N;y++){
            int cnt =0;
            for(int k=0;k<4;k++){
                int nx = x+dx[k];
                int ny = y+dy[k];
                if( nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if( map[nx][ny] != 0 )  cnt++;
            }
            if (cnt < 3) {
                if( map[x][y] != 0) tmp[x][y] = map[x][y] -1;
            }
            else tmp[x][y] = map[x][y];
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            map[i][j] = tmp[i][j];
        }
    }

}

int find_max_lump()
{
    bool visited[MAX][MAX]={0,};
    int res =0;
    queue<pos> q;
    int sum=0;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int cnt =0;
            sum += map[i][j];
            if(map[i][j] <= 0 || visited[i][j] )
                continue;
        
            q.push({i,j});
            visited[i][j]=1;
            
            while(!q.empty()){
                cnt++;
                int x= q.front().x;
                int y= q.front().y;
                q.pop();
                
                for(int k=0;k<4;k++){
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    
                    if( nx < 0 || ny <0 || nx >= N || ny >=N || visited[nx][ny] || map[nx][ny] <= 0)    continue;
                    visited[nx][ny] = 1;
                    q.push({nx,ny});
                }
            }
            if( res < cnt)  res = cnt;
        }
    }
    cout << sum << "\n";
    return res;
}

int main(void)
{
    std::ios::sync_with_stdio(false);

    cin >> N >> Q;
    N = 1 << N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)    cin >> map[i][j];
    }
    for(int i=0;i<Q;i++){
        cin >> L;
        rotate_grid();
        melt_ice();
    }
    cout << find_max_lump();
    return 0;
}