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

문제 링크입니다. https://www.acmicpc.net/problem/20058

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

규칙을 구하는 것이 난이도를 높였던 것 같습니다.

※pow() 함수를 사용하면 시간초과가 됩니다. (1 << X)인 시프트 연산자를 이용해 풀어야 됩니다.

 

이 문제를 푸는 핵심은 부분 격자를 돌리는 방법을 어떻게 찾냐는 것입니다.

격자만 돌릴 줄 안다면, 얼음을 녹이는 것과 얼음 덩이의 크기를 찾는 방법은 매우 간단하기 때문입니다.

 

격자를 돌릴 때, 변하는 좌표에서 일정의 점화식을 찾을 수 있었는데, 이를 유도해보도록 하겠습니다.

N이 3일때를 생각해보겠습니다.

(1, 1)							(1, 8)
			(4, 4)	(4, 5)
			(5, 4)	(5, 5)
(8, 1)							(8, 8)

L이 2일 때, 4*4 크기의 격자로 나눠서 좌표를 변경해야합니다.

(1, 1) ~ (4,4) 까지를 생각해보면

(1, 1) -> (1, 4)  /  (2, 1) -> (1, 3)  /  (3, 1) -> (1, 2)  /  (4, 1) -> (1, 1)

(1, 2) -> (2, 4)  /  (2, 2) -> (2, 3)  /  (3, 2) -> (2, 2)  /  (4, 2) -> (2, 1)

(1, 3) -> (3, 4)  /  (2 ,3) -> (3, 3)  /  (3, 3) -> (3, 2)  /  (4, 3) -> (3, 1)

(1, 4) -> (4, 4)  /  (2, 4) -> (4, 3)  /  (3, 4) -> (4 ,2)  /  (4, 4) -> (4, 1)

이와 같이 좌표가 움직입니다.

 

여기서 하나의 규칙을 찾을 수 있는데,

(A, B) -> (C, D)로 움직일 때, B와 C의 값이 같다는 것과 A + D의 값은 일정하다는 것입니다.

 

(5, 1) ~ (8, 4)까지를 생각해보겠습니다.

(5, 1) -> (5, 4)  /  (6, 1) -> (5, 3)  /  (7, 1) -> (5, 2)  /  (8, 1) -> (5, 1)

(5, 2) -> (6, 4)  /  (6, 2) -> (6, 3)  /  (7, 2) -> (6, 2)  /  (8, 2) -> (6, 1)

(5, 3) -> (7, 4)  /  (6 ,3) -> (7, 3)  /  (7, 3) -> (7, 2)  /  (8, 3) -> (7, 1)

(5, 4) -> (8, 4)  /  (6, 4) -> (8, 3)  /  (7, 4) -> (8 ,2)  /  (8, 4) -> (8, 1)

 

(A, B) -> (C, D)일 때, A + D의 값은 9로 같습니다.

B + 4 = C의 값이 되었습니다.

 

(1, 5) ~ (4, 8)까지 확인해보겠습니다.

(1, 5) -> (1, 8)  /  (2, 5) -> (1, 7)  /  (3, 5) -> (1, 6)  /  (4, 5) -> (1, 5)

(1, 6) -> (2, 8)  /  (2, 6) -> (2, 7)  /  (3, 6) -> (2, 6)  /  (4, 6) -> (2, 5)

(1, 7) -> (3, 8)  /  (2 ,7) -> (3, 7)  /  (3, 7) -> (3, 6)  /  (4, 7) -> (3, 5)

(1, 8) -> (4, 8)  /  (2, 8) -> (4, 7)  /  (3, 8) -> (4 ,6)  /  (4, 8) -> (4, 5)

 

(A, B) -> (C, D)일 때, A + D의 값은 9로 같습니다.

B = C + 4의 값이 되었습니다.

 

이를 통해 A + D의 값을 구할 수 있습니다.

(1, 1) -> (5, 1)일 때, 5 - 1는 4, 1 - 1는 0, 이때 L은 2이니, 2^L + 1 + 4 + 0인 9가 되는 것입니다.

(1, 1) -> (1, 5)일 때, 1 - 1는 0, 5 - 1는 4, 이때 L은 2이니, 2^L + 1 + 0 + 4인 9가 되는 것입니다.

 

B와 C의 관계도 찾을 수 있는데, (1, 1) -> (5, 1)일 때, C = B + 4 - 0,  (1, 1) -> (1, 5)일 때는 C = B + 0 - 4가 되는 것입니다.

 

이를 통해 (5, 5) ~ (8, 8)까지를 확인해본다면

(1, 1)을 기준으로 두었을 때, (5, 5)는 차이가 (4, 4)가 됩니다.

따라서, A + D = 2^2 + 1 + 4 + 4 = 13이 되며, B = C + 4 - 4인 B = C가 된다는 것입니다.

그렇다면, (5, 5) -> (5, 8)로 이동할 것이며, (6, 7) -> (7, 7)로 이동할 것입니다.

 

 

N이 4이며, L이 2일 때, (9, 5) ~ (12, 8)까지 움직이는 것을 생각해보면

(1, 1)을 기준으로 두었을 때, (9, 5)는 차이가 (8, 4)가 됩니다.

따라서, A + D = 2^2 + 1 + 8 + 4 = 17이 되며, C = B + 8 - 4인 C = B + 4가 된다는 것입니다.

그 중 좌표 한개인 (10, 8)은 (12, 7)로 이동할 것입니다.

 

이를 통해 점화식 2개로 나타내면

(X,  Y) 좌표부터 이동하려고 할 때, (1, 1)과 (X, Y)좌표의 차이를 구해줍니다. 이를 x, y라고 한다면

1. x == y

   (A, B) = (B, 2^L+1 + x + y - A)로 이동

2. x != y

   (A, B) = (B + x-  y, 2^L + 1 + x + y - A)로 이동

이를 코드로 나타내면

void move_map(int x, int y, int cnt){
    int X = x - 1, Y = y - 1;
    for(int i = x; i < x + (1<<cnt); i++){
        for(int j = y; j < y + (1<<cnt); j++){
            if(X == Y){
                copy_map[j][(1<<cnt) + 1 + X + Y - i] = map[i][j];
            }
            else{
                copy_map[j+X-Y][(1<<cnt) + 1 + X + Y - i] = map[i][j];
            }
        }
    }
}

해당 코드를 통해 좌표를 옮길 수 있습니다.

 

좌표를 옮겼다면, 얼음을 녹일 차례입니다. 

모든 좌표의 4방향을 확인해 3개 미만인 곳을 전부 찾아주면 됩니다.

 

좌표 옮기고 얼음을 녹이는 과정을 모두 끝냈다면, 얼음 덩어리를 구할 차례입니다,

BFS을 통해, 얼음이 남아있는 곳만 4방향 탐색을 통해 이어줍니다.

 

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, Q, sum;
int map[65][65];
int copy_map[65][65];
int tmp[65][65];
int check[65][65];
int stage[1001];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void move_map(int x, int y, int cnt){
    int X = x - 1, Y = y - 1;
    for(int i = x; i < x + (1<<cnt); i++){
        for(int j = y; j < y + (1<<cnt); j++){
            if(X == Y){
                copy_map[j][(1<<cnt) + 1 + X + Y - i] = map[i][j];
            }
            else{
                copy_map[j+X-Y][(1<<cnt) + 1 + X + Y - i] = map[i][j];
            }
        }
    }
}

void melt_ice(){
    for(int i = 1; i <= (1<<N); i++){
        for(int j = 1; j <= (1<<N); j++){
            if(copy_map[i][j] == 0){
                map[i][j] = copy_map[i][j];
                continue;
            }
            int cnt = 0;
            for(int k = 0; k < 4; k++){
                int xx = i + dx[k];
                int yy = j + dy[k];
                if(xx >= 1 && xx <= (1<<N) && yy >= 1 && yy <= (1<<N)){
                    if(copy_map[xx][yy] > 0) cnt++;
                }
            }
            if(cnt < 3){
                if(copy_map[i][j] > 0){ 
                    map[i][j] = copy_map[i][j] - 1;
                    sum--;
                }
            }
            else map[i][j] = copy_map[i][j];
        }
    }
}

int bfs(int X, int Y){
    queue<P> q;
    int cnt = 0;
    q.push({X, Y});
    check[X][Y] = 1;
    while(!q.empty()){
        int x = q.front().F;
        int y = q.front().S;
        cnt++;
        q.pop();
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= (1<<N) && yy >= 1 && yy <= (1<<N)){
                if(check[xx][yy] == 0 && map[xx][yy] > 0){
                    check[xx][yy] = 1;
                    q.push({xx, yy});
                }
            }
        }
    }
    return cnt;
}

void solve(){
    for(int k = 1; k <= Q; k++){
        for(int i = 1; i <= (1<<N); i += (1<<stage[k])){
            for(int j = 1; j <= (1<<N); j += (1<<stage[k])){
                move_map(i, j, stage[k]);
            }
        }
        melt_ice();
    }
    int maxi = 0;
    for(int i = 1; i <= (1<<N); i++){
        for(int j = 1; j <= (1<<N); j++){
           if(check[i][j] == 0 && map[i][j] > 0) maxi = max(maxi, bfs(i, j));
        }
    }
    cout << sum << "\n" << maxi;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> Q;
    for(int i = 1; i <= (1<<N); i++){
        for(int j = 1; j <= (1<<N); j++){
            cin >> map[i][j];
            sum += map[i][j];
        }
    }
    for(int i = 1; i <= Q; i++)  cin >> stage[i];
    solve();
    return 0;
}

 

질문 및 조언은 댓글을 남겨주세요