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

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

www.acmicpc.net/problem/20058

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

 

 

 문제

 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법을 시전하기 전	L = 1	L = 2

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

 

 

 

 입력

 첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

 마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

 

• 2 ≤ N ≤ 6
• 1 ≤ Q ≤ 1,000
• 0 ≤ A[r][c] ≤ 100
• 0 ≤ Li ≤ N

 

 출력

 첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

 

 

 풀이

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

int N, Q, n;
int arr[64][64];
int L[1000];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
bool check[64][64];

void input_set(){
	cin >> N >> Q;
	n = 1<<N;
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin >> arr[i][j];
		}
	}
	for(int i=0;i<Q;i++){
		cin >> L[i];
	}
	
	return;
}

void rotate(int type){
	int temp[64][64] = {0,};
	int temp2[64][64] = {0,};
	
	int len = 1<<type;
	for(int i=0;i<n;i+=len){
		for(int j=0;j<n;j+=len){
			for(int q=i;q<i+len;q++){
				for(int w=j;w<j+len;w++){
					temp2[q-i][w-j] = arr[q][w];
				}
			}
			for(int a=0;a<len;a++){
				for(int b=0;b<len;b++){
					temp[a][b] = temp2[len-1-b][a];
				}
			}
			for(int q=i;q<i+len;q++){
				for(int w=j;w<j+len;w++){
					arr[q][w] = temp[q-i][w-j];
				}
			}
		}
	}
}

void melt(){
	bool flag[64][64] = {false,};
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(arr[i][j] == 0) continue;
			int cnt = 0;
			for(int k=0;k<4;k++){
				int ii = i + dx[k];
				int jj = j + dy[k];
				if(ii < 0 || ii >=n || jj < 0 || jj >= n) continue;
				
				if(arr[ii][jj] > 0) cnt++;
			}
			
			if(cnt < 3) flag[i][j] = true;
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(flag[i][j]) arr[i][j]--;
		}
	}
}

int bfs(int i, int j){
	queue<pair<int, int>> q;
	int cnt = 0;
	
	q.push(make_pair(i, j));
	check[i][j] = true;
	cnt++;
	
	while(!q.empty()){
		int a = q.front().first;
		int b = q.front().second;
		q.pop();
		
		for(int k=0;k<4;k++){
			int aa = a + dx[k];
			int bb = b + dy[k];
			if(aa < 0 || aa >= n || bb < 0 || bb >= n) continue;
			if(check[aa][bb]) continue;
			
			if(arr[aa][bb] > 0){
				q.push(make_pair(aa, bb));
				check[aa][bb] = true;
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	input_set();
	for(int i=0;i<Q;i++){
		rotate(L[i]);
		melt();
	}

	int s = 0;
	int target = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			s += arr[i][j];
			if(arr[i][j] > 0 && !check[i][j]){
				int v = bfs(i, j);
				if(v > target) target = v;
			}
		}
	}
	cout << s << '\n' << target;
	return 0;
}

 회전 구현을 처음 해본 문제이다. 구현해야하는 부분은 다음과 같다.

 

1. 회전

: L 값에 따라 회전하는 배열의 크기가 바뀐다. int len = 1<<type 이라는 한 줄로 2^type을 쉽게 구할 수 있다. temp배열을 만들어서 회전에 따른 i, j 변화를 파악하여 값을 대입해 주면 회전을 구현할 수 있다. 인덱스의 변화는 배열을 하나 직접 그려서 생각해보면 쉽다.

 

2. 얼음 녹음

: 이차원 배열 전체에 대해 하나씩 확인한다. 사방에 0이 아닌 값, 즉 얼음이 있으면 카운트하고 3개 이상이 되지 않으면 값을 1 감소한다. 끝이다.

 

3. 가장 큰 덩어리 찾기

: 단순 BFS로 구현가능하다.

 

은근 쉽게 푼 것으로 보아 구현 문제에 꽤나 익숙해진것 같아서 기분이 좋았다.