[백준/c++] 20058 마법사 상어와 파이어스톰

문제

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

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

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

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

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

입력

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

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

출력

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

제한

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

 

구현해야할 조건

비트를 사용해서 제곱을 구하면 조금이나마 간단하다. 시계 방향으로 90도 회전시킨다, 90도 반시계 방향으로 회전시킨다는 내가 이 내용을 잘 공부하지 못해서 조금 헤매고 결국 찾아볼수 밖에 없었는데 다음부터는 찾아보지 않고 구현해보자! 그리고 얼음이 있는 칸 3개 또는 그 이상과 인접해 있지 않은 칸은 얼음의 양이 1 줄어드는데, 여기서 함정이 있었다. 한번에 모든 얼음이 줄어드는 것이지 한칸 줄어들고 한칸 줄어드는 것이 아니다. 이점을 유의하자! 항상 두 세번 디버깅을 해야지 생각이 나는데 이점을 꼭 유의하자! 그리고 남아있는 얼음의 합은 단순히 이중 for문 돌리고, 남아있는 얼음중 가장 큰 덩어리는 DFS, BFS를 사용해서 구해보자!

 

code

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>

#define MAX 75
using namespace std;

const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0}; // down, up, right, left

int n,q;
int res = 0;
int board[MAX][MAX];
int tempBoard[MAX][MAX];
int tempMelt[MAX][MAX];
bool visited[MAX][MAX];

// 한번할 때마다 얼음이 녹는 것이 아니라, 한번에 지워줘야 하기 때문에 배열을 새롭게 사용해야 한다.
// 이점을 유의하자! 항상 이런 함정이 존재하니까! 
// 90도 회전하는것 생각하자 정말로!! 

void rotate_board(int y, int x, int l)
{
	for(int i = 0; i < l; i++)
	{
		for(int j = 0; j < l; j++)
		{			
			tempBoard[j][l - 1 - i] = board[i+y][j+x]; // 여기 구현방식에서 많이 헤맸다. 왜 i,j를 0부터? tempBoard때문에 편안하게 하기 위해서
		}
	}
	
	for(int i = 0; i < l; i++)
	{
		for(int j = 0; j < l; j++)
		{
			board[y+i][x+j] = tempBoard[i][j];
		}
	}
} 

void melting(int y, int x, int n)
{
	int cnt = 0;
	
	for(int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i]; // 4 direction move
		
		if(0 <= nx && nx < n && 0 <= ny && ny < n) // in range
		{
			if(board[ny][nx] != 0) // not zero
				cnt++;
		}
	}
	
	if(cnt < 3)
		tempMelt[y][x] = 1; // tempMelt 배열을 만들어줘서 나중에 한번에 빼주자!
}

void DFS(int y, int x, int n, int cnt) // 돌아가지 않은 코드 귀찮아서 BFS로 돌렸다
{
	visited[y][x] = true;
	
	if(res < max(res,cnt))
		res = cnt;
	
	for(int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(0 <= nx && nx < n && 0 <= ny && ny < n)
		{
			if(!visited[ny][nx] && board[ny][nx] != 0)
			{
				visited[ny][nx] = true;
				DFS(ny,nx,n,cnt+1);
			}
		}
	}
}

void BFS(int y, int x, int n) // 가장 큰 개수를 구하는 방법
{
	queue<pair<int,int> > q;
	q.push({y,x});
	
	int cnt = 1;
	visited[y][x] = true;
	
	while(!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		
		
		for(int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(0 <= nx && nx < n && 0 <= ny && ny < n)
			{
				if(!visited[ny][nx] && board[ny][nx] != 0)
				{
					visited[ny][nx] = true;
					q.push({ny,nx});
					cnt += 1;
				}
			}
		}
	}
	
	if(res < cnt)
		res = cnt;
}

int main()
{
	cin >> n >> q;
	
	int len = 1 << n; // 비트를 이용해 제곱수 쉽게 구하기 물론,2의 제곱수
	
	for(int i = 0; i < len; i++)
	{
		for(int j = 0; j < len; j++)
		{
			cin >> board[i][j];
		}
	}
	
	int num = 0;
	
	for(int i = 0; i < q; i++)
	{
		memset(visited,0,sizeof(visited));	
		memset(tempMelt,0,sizeof(tempMelt));
		cin >> num;
		
		int length = 1 << num; 
		
		for(int i = 0; i < len; i+=length)
		{
			for(int j = 0; j < len; j+=length)
			{ 	
				rotate_board(i,j,length); // 90도 회전
			}
		} // 90도 회전 
		
		for(int i = 0; i < len; i++)
		{
			for(int j = 0; j < len; j++)
			{
				if(board[i][j] != 0) // ice is not zero!
					melting(i,j,len);
			}
		}
		
		for(int i = 0; i < len; i++)
		{
			for(int j = 0; j < len; j++)
			{
				board[i][j] -= tempMelt[i][j];
			}
		}
	}
	
	int sum = 0;
		
	for(int i = 0; i < len; i++)
		for(int j = 0; j < len; j++)
			sum += board[i][j];

	for(int i = 0; i < len; i++)
	{
		for(int j = 0; j < len; j++)
		{
			if(!visited[i][j] && board[i][j] != 0)
				BFS(i,j,len);	
		}
	}
					
	cout << sum << "\n";
	cout << res << "\n";
	
	return 0;
}

 

code [다르게 푼 방식인데, 항상 주의해야할건 동시에 지워진다는것을 유의하자!]

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>

#define MAX 1<<7 // 비트연산자로 MAX값 구해주고 
using namespace std;

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

int n,Q,res;
int n_size;

int board[MAX][MAX];
int tempMelt[MAX][MAX];
bool visited[MAX][MAX];

void clock(int y, int x, int size)
{
	/*
	잘 생각해서 문제를 해결해야합니다. 일반적으로 board를 돌려주는 것보다
	temp를 돌려서 문제를 해결하는게 속 편합니다. 일반적으로 돌려주는 방식으로 했다가
	범위가 헷갈려 시간을 많이 뺏겼습니다. 
	*/
	
	int temp[MAX][MAX];
	
	for(int i = 0; i < size; i++){
		for(int j = 0; j < size; j++){
			temp[j][size - 1 - i] = board[i+y][j+x];
		}
	}
	
	for(int i = 0; i < size; i++){
		for(int j = 0; j < size; j++){
			board[i+y][j+x] = temp[i][j];
		}
	}
	
} 

void melting(int y, int x)
{
	int cnt = 0; // 얼음이 주변에 있나요?
	
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(0 <= nx && nx < n_size && 0 <= ny && ny < n_size)
		{
			if(board[ny][nx] != 0)
				cnt++;
		}
	}
	
	if(cnt < 3) // 주변에 얼음이 3개 이상 없으면? 
		tempMelt[y][x] = 1;
}

void BFS(int y, int x, int n)
{
	queue<pair<int,int> > q;
	q.push({y,x});
	
	int cnt = 1;
	visited[y][x] = true;
	
	while(!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(0 <= nx && nx < n && 0 <= ny && ny < n){
				if(!visited[ny][nx] && board[ny][nx] != 0){
					visited[ny][nx] = true;
					q.push({ny,nx});
					cnt += 1;
				}
			}
		}
	}
	
	if(res < cnt)
		res = cnt;
}

int main()
{
	cin >> n >> Q;
	
	n_size = 1 << n; // 2의 제곱으로 들어가기 때문에 bit연산자를 사용했습니다. 
	
	for(int i = 0; i < n_size; i++){
		for(int j = 0; j < n_size; j++){
			cin >> board[i][j];
		}
	}
	
	int pow = 0;
	
	while(Q--)
	{
		memset(visited,0,sizeof(visited)); // 방문됐는지 확인하는 값
		memset(tempMelt,0,sizeof(tempMelt)); // 매 주문마다 새롭게 만들어야함
		
		cin >> pow;
		
		int pow_size = 1 << pow; // 각각 돌려야할 범위를 설정
		
		for(int i = 0; i < n_size; i+=pow_size){
			for(int j = 0; j < n_size; j+=pow_size){
				clock(i,j,pow_size); // 시계방향으로 돌리는 함수, 전체 돌려주기 
			}
		}
		
		for(int i = 0; i < n_size; i++){
			for(int j = 0; j < n_size; j++){
				if(board[i][j] != 0){
				 // 0이 아닐때, melting을 생각해야합니다. 0은 더이상 녹을 이유가 없죠 
					melting(i,j); 
				}
			}
		}
		
		for(int i = 0; i < n_size; i++){
			for(int j = 0; j < n_size; j++){
				board[i][j] -= tempMelt[i][j]; // 녹은 얼음들을 빼줍니다. 동시에 사라진다는것을 명심, 먼저 사라지면 저어어얼대 안돼!
			}
		}
	}
	
	
	int sum = 0; // 전체적으로 끝났으면, 얼음의 양과, 가장 넓은 범위를 구해줍시다.
	
	for(int i = 0; i < n_size; i++){
		for(int j = 0; j < n_size; j++){
			sum += board[i][j];
		}
	} 
	
	for(int i = 0; i < n_size; i++){
		for(int j = 0; j < n_size; j++){
			
			if(!visited[i][j] && board[i][j] != 0) // 방문된적 없고, board가 0이 아니면 즉, 얼음이 있으면
				BFS(i,j,n_size);
		}
	}
	
	cout << sum << "\n";
	cout << res;
	
	
	return 0;
}