백준 - 20058 [C++]

 이 문제는 시뮬레이션과 BFS를 이용한 문제이다. 이 문제는 그렇게 어렵지 않은 문제였으나 두가지 주의해야할 점이 있었다.

 

 첫번째는 solve() 안에서 녹을 얼음을 고르는 로직에서 한번에 A 배열에 결과를 반영하면 다음 반복문에서 그 영향을 받아 연쇄적으로 값이 줄어든다. 그러므로 녹을 얼음을 체크만 해놓고 모든 체크가 끝나면 한꺼번에 1을 감소시켜야 한다. 

 

 두번째는 저렇게 로직을 짜도 시간 초과가 떴는데, 이는 로직의 문제가 아니라 cmath 내장 함수 pow를 쓰면 시간 초과가 난다. 직접 만들어서 쓰면 시간 초과가 안 뜬다. 애초에 배열의 크기도 매우 작고, 시간 복잡도를 계산해봐도 절대 1초를 넘기지 않는다. 수학 내장 함수는 조심해서 써야할 것 같다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>

using namespace std;

int N, Q;
int A[64][64];
bool visited[64][64];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

int pow(int n, int p)
{
	switch (p)
	{
	case 0:
		return 1;
	case 1:
		return 2;
	case 2:
		return 4;
	case 3:
		return 8;
	case 4:
		return 16;
	case 5:
		return 32;
	case 6:
		return 64;
	}
}

bool inRange(int y, int x)
{
	int num = pow(2, N);

	if (0 <= y && y < num && 0 <= x && x < num)
	{
		return true;
	}
	return false;
}

void divideAndRoll(int startY, int startX, int endY, int endX, int l)
{
	vector<vector<int>> result;

	for (int x = startX; x < endX; x++)
	{
		vector<int> temp;

		for (int y = endY - 1; y >= startY; y--)
		{
			temp.push_back(A[y][x]);
		}

		result.push_back(temp);
	}

	int indexY = 0, indexX = 0;
	for (int y = startY; y < endY; y++)
	{
		for (int x = startX; x < endX; x++)
		{
			A[y][x] = result[indexY][indexX++];
		}
		indexY++;
		indexX = 0;
	}
}

int bfs(int startY, int startX)
{
	queue<pair<int, int>> q;

	visited[startY][startX] = true;
	int cnt = 1;

	q.push({ startY, startX });

	while (!q.empty())
	{
		pair<int, int> present = q.front();
		q.pop();

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

			if (inRange(ny, nx) && !visited[ny][nx] && A[ny][nx] > 0)
			{
				q.push({ ny, nx });
				visited[ny][nx] = true;
				cnt++;
			}
		}
	}

	return cnt;
}

void solve(int L)
{
	// 1. divide and roll
	int num = pow(2, N);
	int l = pow(2, L);
	for (int y = 0; y < num; y += l)
	{
		for (int x = 0; x < num; x += l)
		{
			divideAndRoll(y, x, y + l, x + l, l);
		}
	}

	// 2. find adjacent and melt
	vector<pair<int, int>> melt;

	for (int y = 0; y < num; y++)
	{
		for (int x = 0; x < num; x++)
		{
			if (A[y][x] > 0)
			{
				int cnt = 0;

				for (int i = 0; i < 4; i++)
				{
					int ny = y + dy[i];
					int nx = x + dx[i];

					if (inRange(ny, nx) && A[ny][nx] > 0)
					{
						cnt++;
					}
				}

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

	for (auto &m : melt)
	{
		A[m.first][m.second]--;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> Q;

	int num = pow(2, N);

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

	for (int q = 0; q < Q; q++)
	{
		int L;

		cin >> L;
		solve(L);
	}

	int answer1 = 0;
	int answer2 = 0;
	
	for (int y = 0; y < num; y++)
	{
		for (int x = 0; x < num; x++)
		{
			answer1 += A[y][x];

			if (!visited[y][x] && A[y][x] > 0)
			{
				answer2 = max(answer2, bfs(y, x));
			}
		}
	}

	cout << answer1 << '\n' << answer2 << '\n';
	
	return 0;
}