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

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

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

해리포터 상어와 마법사의 돌

 

소요 시간

골드 2 기준 문제 해석부터 맞았습니다! 까지 52분이 소요되었습니다.

딱 골드 4정도 문제였던 것 같네요. 중간에 얼음이 녹는 부분이 동시에 일어나야 한다는 점을 빼먹는 바람에 디버깅에 시간이 좀 걸렸습니다. "동시에 일어난다" 같은 표현이 없어도 당연히 동시에 녹는 걸로 판단해야 하는데, 잘못했네요... 반성합니다.

시뮬레이션 문제는 골드 2~3은 1시간, 골드 4~5는 40분만에 "확실하게" 풀고 싶은데, 아직 내공이 부족한 것 같습니다.

 

구상

1. 파이어스톤 함수

- 전체를 2^L * 2^L 부분 격자로 나눕니다.

    - x, y각각 0부터 시작해서 2*L씩 더해 가면서 각 격자의 좌상단을 구합니다.

- 구해진 좌상단들을 통해 rotate함수를 호출하여 각 부분격자를 회전시킵니다.

- 얼음을 1 녹이는 함수 호출

- 합을 구합니다.

- 덩어리 크기를 계산하는 함수 호출

- 합과 크기 리턴

 

2. 시계방향으로 90도 rotate하는 함수

- 90도 rotate면 각 (x,y)를 (y,N-x-1)자리로 옮기면 됩니다.

- 이걸 하나의 배열 위에 진행하면 아직 변환되지 않은 값이 corrupt 됩니다.

- 따라서 임시배열을 만들어서 변환값을 저장하고 그 변환값을 다시 원 배열에 넣어 줍니다.

 

3. 전체 얼음에서 인접영역 얼음이 3개 미만인 얼음을 1만큼 녹이는 함수

- 항상 하던 대로 상하좌우 검사해서 인접영역의 얼음 개수를 구합니다.

- 얼음 개수가 3보다 작은 칸들은 따로 표시를 해두고 마지막에 한번에 -1 해줍니다.

 

4. 가장 큰 덩어리의 크기를 계산하는 함수

- 기본적으로 bfs를 해야 합니다. (이런 종류의 구역 나누기 문제는 주로 bfs 사용합니다. 방문만 하면 되기 때문)

- 모든 얼음을 방문할 때까지 얼음이 있으면서 방문하지 않은 칸마다 bfs로 연결된 얼음을 방문합니다.

 

5. 얼음의 합을 구하는 것은 귀찮아서 함수를 만들지 않았습니다.

- 루프문 두개 돌려서 할 수 있습니다.

 

코드

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

using namespace std;

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

void do_rotate(int x, int y, int len, vector<vector<int> >& ices) {
    vector<vector<int> > temp; 
    temp.resize(len);
    for(int i=0; i<len; i++) {
        temp[i].resize(len);
    }
    for(int i=x; i<x+len; i++) {
        for(int j=y; j<y+len; j++) {
            temp[j-y][len-(i-x)-1] = ices[i][j];
        }
    }
    for(int i=x; i<x+len; i++) {
        for(int j=y; j<y+len; j++) {
            ices[i][j] = temp[i-x][j-y];
        }
    }
}

void remove_ice(int N, vector<vector<int> >& ices) {
    int total = pow(2, N);
    vector<vector<int> > add;
    add.resize(total);
    for(int i=0; i<total; i++) {
        add[i].resize(total);
    }
    for(int i=0; i<total; i++) {
        for(int j=0; j<total; j++) {
            if(ices[i][j] == 0) continue;
            int numOfIce = 0;
            for(int k=0; k<4; k++) {
                int nx = i + dx[k]; int ny = j + dy[k];
                if(nx < 0 || nx > total-1 || ny < 0 || ny > total - 1 || ices[nx][ny] == 0) continue;
                else numOfIce ++;
            }
            if(numOfIce < 3)
                add[i][j] -= 1;
        }
    }

    for(int i=0; i<total; i++) {
        for(int j=0; j<total; j++) {
            ices[i][j] += add[i][j];
        }
    }
}

void do_firestrom(int N, int L, vector<vector<int> >& ices) {
    int len = pow(2, L);
    int total = pow(2, N);
    for(int i=0; i<total; i+= len) {
        for(int j=0; j<total; j+= len) {
            do_rotate(i, j, len, ices);
        }
    }
    remove_ice(N, ices);
}

int find_largest(int N, vector<vector<int> >& ices) {
    int largest = 0;
    int total = pow(2, N);
    bool visited[total][total];
    for(int i=0; i<total; i++) {
        fill_n(visited[i], total, false);
    }

    for(int i=0; i<total; i++) {
        for(int j=0; j<total; j++) {
            if(ices[i][j] != 0 && !visited[i][j]) {
                int ice_size = 0;
                queue<int> q; q.push(i*total + j);
                visited[i][j] = true;
                while(!q.empty()) {
                    int x = q.front()/total; int y = q.front()%total;
                    ice_size ++;
                    q.pop();
                    for(int k=0; k<4; k++) {
                        int nx = x + dx[k]; int ny = y + dy[k];
                        if(nx < 0 || nx > total-1 || ny < 0 || ny > total-1 || visited[nx][ny] || ices[nx][ny] == 0) continue;
                        visited[nx][ny] = true;
                        q.push(nx*total + ny);
                    }
                }
                largest = max(ice_size, largest);
            }
        }
    }

    return largest;
}

vector<int> solution(int N,int Q,vector<vector<int> >& ices, vector<int>& commands) {
    vector<int> answer; answer.resize(2);
    int total = pow(2, N);
    for(int i=0; i<Q; i++) {
        int L = commands[i];
        do_firestrom(N, L, ices);
    }

    for(int i=0; i<total; i++) {
        for(int j = 0; j<total; j++) {
            answer[0] += ices[i][j];
        }
    }
    answer[1] = find_largest(N, ices);

    return answer;
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N, Q;
    cin >> N >> Q;
    int total = pow(2, N);

    vector<vector<int> > ices;
    ices.resize(total);
    for(int i=0; i<total; i++) {
        ices[i].resize(total);
        for(int j=0; j<total; j++) {
            cin >> ices[i][j];
        }
    }
    vector<int> commands;
    commands.resize(Q);
    for(int i=0; i<Q; i++) {
        cin >> commands[i];
    }
    
    vector<int> result = solution(N, Q, ices, commands);
    cout << result[0] << "\n" << result[1] << "\n";

    return 0;
}