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

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

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

기존 마법사 상어 문제들과 비슷한 유형이었습니다.

 

알고리즘은 아래와 같습니다.

1. 격자를 2^L * 2^L 크기의 부분 격자로 나눈 뒤 시계 방향으로 돌려줍니다. (rotate 메서드)

2. 파이어스톰을 시전합니다. (firestorm 메서드)

3. 1 ~ 2번 과정을 Q번 반복해줍니다.

4. 격자 내 모든 얼음 크기의 합을 구한 뒤 출력해주고 (getIceCnt 메서드)

5. 가장 큰 덩어리의 크기를 구한 뒤 출력해줍니다. (getLargestComponent 메서드)

 

이 문제에서의 핵심은 1번 알고리즘 즉, 2^L * 2^L 크기의 부분 격자로 나눈 뒤 회전시키는 알고리즘인데 해당 알고리즘은 아래와 같습니다.

 

	void rotate(int y, int x, int l)
	{
	int tempA[MAX][MAX];
	// 기존 2^L * 2^L 격자 복사
	for (int i = y; i < y + (1 << l); i++)
	{
	for (int j = x; j < x + (1 << l); j++)
	{
	tempA[i][j] = A[i][j];
	}
	}
	// 회전시키는 알고리즘
	for (int i = y; i < y + (1 << l); i++)
	{
	for (int j = x; j < x + (1 << l); j++)
	{
	A[j - x + y][y + (1 << l) - (i + 1) + x] = tempA[i][j];
	}
	}
	}

view raw .cpp hosted with ❤ by GitHub

전체 소스코드

 

	#include <iostream>
	#include <queue>
	#include <algorithm>
	using namespace std;
	const int MAX = 64;
	typedef struct
	{
	int y, x;
	} Coord;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
	int N;
	int A[MAX][MAX];
	bool visited[MAX][MAX];
	void rotate(int y, int x, int l)
	{
	int tempA[MAX][MAX];
	for (int i = y; i < y + (1 << l); i++)
	{
	for (int j = x; j < x + (1 << l); j++)
	{
	tempA[i][j] = A[i][j];
	}
	}
	for (int i = y; i < y + (1 << l); i++)
	{
	for (int j = x; j < x + (1 << l); j++)
	{
	A[j - x + y][y + (1 << l) - (i + 1) + x] = tempA[i][j];
	}
	}
	}
	void fireStorm(void)
	{
	queue<Coord> q;
	for (int y = 0; y < (1 << N); y++)
	{
	for (int x = 0; x < (1 << N); x++)
	{
	if (A[y][x] == 0)
	{
	continue;
	}
	int adjacentIceCnt = 0;
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= (1 << N) || nextX < 0 || nextX >= (1 << N))
	{
	continue;
	}
	if (A[nextY][nextX])
	{
	adjacentIceCnt++;
	}
	}
	if (adjacentIceCnt < 3)
	{
	q.push({ y, x });
	}
	}
	}
	while (!q.empty())
	{
	int y = q.front().y;
	int x = q.front().x;
	q.pop();
	A[y][x]--;
	}
	}
	int getIceSum(void)
	{
	int result = 0;
	for (int i = 0; i < (1 << N); i++)
	{
	for (int j = 0; j < (1 << N); j++)
	{
	result += A[i][j];
	}
	}
	return result;
	}
	int BFS(int y, int x)
	{
	queue<Coord> q;
	q.push({ y, x });
	visited[y][x] = true;
	int cnt = 0;
	while (!q.empty())
	{
	int curY = q.front().y;
	int curX = q.front().x;
	q.pop();
	cnt++;
	for (int k = 0; k < 4; k++)
	{
	int nextY = curY + moveDir[k].y;
	int nextX = curX + moveDir[k].x;
	if (nextY < 0 || nextY >= (1 << N) || nextX < 0 || nextX >= (1 << N))
	{
	continue;
	}
	if (visited[nextY][nextX] || A[nextY][nextX] == 0)
	{
	continue;
	}
	visited[nextY][nextX] = true;
	q.push({ nextY, nextX });
	}
	}
	return cnt;
	}
	int getLargentComponent(void)
	{
	int result = 0;
	for (int y = 0; y < (1 << N); y++)
	{
	for (int x = 0; x < (1 << N); x++)
	{
	if (visited[y][x] || A[y][x] == 0)
	{
	continue;
	}
	result = max(result, BFS(y, x));
	}
	}
	return result;
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int Q;
	cin >> N >> Q;
	for (int i = 0; i < (1 << N); i++)
	{
	for (int j = 0; j < (1 << N); j++)
	{
	cin >> A[i][j];
	}
	}
	for (int q = 0; q < Q; q++)
	{
	int L;
	cin >> L;
	for (int y = 0; y < (1 << N); y += (1 << L))
	{
	for (int x = 0; x < (1 << N); x += (1 << L))
	{
	rotate(y, x, L);
	}
	}
	fireStorm();
	}
	cout << getIceSum() << "\n";
	cout << getLargentComponent() << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~