🙇‍♀️[Gold III] 마법사 상어와 파이어스톰 - 20058

문제 링크

성능 요약

메모리: 2500 KB, 시간: 64 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션

제출 일자

2024년 3월 18일 19:41:50

문제 설명

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 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가 순서대로 주어진다.

출력

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

🚀풀이

문제를 이해못해서 오래걸린 문제..

회전의 뜻을 잘 이해못해서 덩어리 단위로 회전하는 줄 알았는데 알고보니 덩어리 내부를 회전시키는거였다..

행렬회전은 공식이 있었는데 까먹어서 구글링을 했다.

ps에 자주 나오기 때문에 정리를 한번해야겠다.

문제에서 회전하는 함수는 아래와 같이 구현한다.

void rotate(int y1, int x1, int size)
{
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
        {
			clone[y1 + j][x1 + size - i - 1] = board[y1 + i][x1 + j];
        }
	}
}

DFS와 BFS, 행렬 회전까지 섞인 문제로 잘 만든 문제였다.

image

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>

using namespace std;

int N, Q, L, board_size, mass = 0;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
vector<vector<int>> board;
vector<vector<bool>> visited;
int clone[200][200];

void rotate(int y1, int x1, int size)
{
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
			clone[y1 + j][x1 + size - i - 1] = board[y1 + i][x1 + j];
	}
}

void DFS(int y, int x, int size)
{
	if (size == pow(2, L))
	{
		// L단계만큼 쪼개졌다.
		rotate(y, x, size);

		for (int i = 0; i < size; ++i)
		{
			for (int j = 0; j < size; ++j)
			{
				board[y + i][x + j] = clone[y + i][x + j];
			}
		}

		return;
	}
	else
	{
		// L단계만큼 쪼개지지 않았다.
		DFS(y, x, size / 2);
		DFS(y + size / 2, x, size / 2);
		DFS(y, x + size / 2, size / 2);
		DFS(y + size / 2, x + size / 2, size / 2);
	}
}

void melt()
{
	vector<pair<int, int>> temp;

	for (int y = 0; y < board_size; ++y)
	{
		for (int x = 0; x < board_size; ++x)
		{
			// 인접한 얼음의 개수
			int cnt = 0;
			for (int k = 0; k < 4; ++k)
			{
				int ny = y + dy[k];
				int nx = x + dx[k];

				if (ny < 0 || nx < 0 || ny > board_size - 1 || nx > board_size - 1)
					continue;
				if (board[ny][nx] == 0)
					continue;

				cnt++;
			}

			if (cnt < 3)
			{
				temp.push_back({ y, x });
			}
		}
	}

	for (int i = 0; i < temp.size(); ++i)
	{
		board[temp[i].first][temp[i].second]--;
		if (board[temp[i].first][temp[i].second] < 0)
			board[temp[i].first][temp[i].second] = 0;
	}
}

void BFS(int y, int x)
{
	int cnt = 0;
	queue<pair<int, int>> q;
	if (visited[y][x] == true || board[y][x] == 0)
		return;
	visited[y][x] = true;
	q.push({ y, x });
	pair<int, int> here;

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();
		visited[here.first][here.second] = true;
		cnt++;
		mass = max(mass, cnt);

		for (int i = 0; i < 4; ++i)
		{
			int ny = here.first + dy[i];
			int nx = here.second + dx[i];

			if (ny < 0 || nx < 0 || ny > board_size - 1 || nx > board_size - 1)
				continue;
			if (visited[ny][nx] == true)
				continue;
			if (board[ny][nx] == 0)
				continue;

			q.push({ ny, nx });
			visited[ny][nx] = true;
		}
	}
}

void solve()
{
	cin >> N >> Q;
	board_size = pow(2, N);
	board = vector<vector<int>>(board_size, vector<int>(board_size));
	visited = vector<vector<bool>>(board_size, vector<bool>(board_size, false));

	for (int y = 0; y < board_size; ++y)
	{
		for (int x = 0; x < board_size; ++x)
		{
			cin >> board[y][x];
		}
	}

	for (int i = 0; i < Q; ++i)
	{
		cin >> L;

		// 쪼개고 회전하기
		DFS(0, 0, board_size);

		//얼음 녹이기
		melt();
	}

	// 남아있는 얼음의 합
	int sum = 0;
	for (int y = 0; y < board_size; ++y)
	{
		for (int x = 0; x < board_size; ++x)
		{
			sum += board[y][x];
		}
	}
	cout << sum << '\n';

	// 최대 덩어리
	for (int y = 0; y < board_size; ++y)
	{
		for (int x = 0; x < board_size; ++x)
		{
			BFS(y, x);
		}
	}
	cout << mass << '\n';
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}

참고