상어 중학교 (feat. 백준, 21609번)

상어 중학교
https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/21609
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Block {
	int x, y;
};
class BlockGroup {
public:
	BlockGroup() : total_count(0) {}
public:
	vector<Block> rainbow_blocks;
	vector<Block> normal_blocks;
	int total_count;
};
int N, M, arr[21][21], arr_tmp[21][21], visit[21][21], dx[4], dy[4], result;
inline bool cmp(const BlockGroup& v1, const BlockGroup& v2) {
	if (v1.total_count == v2.total_count) {
		if (v1.rainbow_blocks.size() == v2.rainbow_blocks.size()) {
			if (v1.normal_blocks[0].x == v2.normal_blocks[0].x)
				return v1.normal_blocks[0].y > v2.normal_blocks[0].y;
			return v1.normal_blocks[0].x > v2.normal_blocks[0].x;
		}
		return v1.rainbow_blocks.size() > v2.rainbow_blocks.size();
	}
	return v1.total_count > v2.total_count;
}
inline void make_block_group(int x, int y, const int& value, BlockGroup& out) {
	auto nx = 0, ny = 0;
	Block block{x, y};
	queue<Block> q;
	q.push(block);
	visit[x][y] = 2;					// 이미 방문했고 재방문 불가능하도록 함
	++out.total_count;
	out.normal_blocks.push_back(block);
	while (!q.empty()) {
		block = q.front(); q.pop();
		x = block.x, y = block.y;
		for (auto idx = 0; idx < 4; ++idx) {
			nx = x + dx[idx], ny = y + dy[idx];
			if (1 <= nx && nx <= N && 1 <= ny && ny <= N && !visit[nx][ny] && (arr[nx][ny] == value || arr[nx][ny] == 0)) {
				++out.total_count, block.x = nx, block.y = ny, q.push(block);
				if (arr[nx][ny] == value)		out.normal_blocks.push_back(block), visit[nx][ny] = 2;		// 일반 블록은 재방문 불가능하도록
				else							out.rainbow_blocks.push_back(block), visit[nx][ny] = 1;		// 무지개 블록은 방문 표시만
			}
		}
	}
	// 블록그룹은 최소 2개가 묶여야함
	if (out.total_count == 1)
		return;

	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			if (visit[ix][iy] == 1)			// 방문한것들 가운데 무지개 블록은 재방문 가능하도록 함
				visit[ix][iy] = 0;
}
inline void delete_block_group(const BlockGroup& group) {
	for (const auto& v : group.rainbow_blocks)
		arr[v.x][v.y] = -2;				// 지운 블록칸은 -2로 표시
	for (const auto& v : group.normal_blocks)
		arr[v.x][v.y] = -2;				// 지운 블록칸은 -2로 표시
}
inline bool find_max_block_group() {
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			visit[ix][iy] = 0;
	vector<BlockGroup> store;
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			// 방문한적이 없고, 일반 블록일때만 bfs를 수행
			if (!visit[ix][iy] && arr[ix][iy] > 0) {
				BlockGroup block_group;
				make_block_group(ix, iy, arr[ix][iy], block_group);
				// 기존의 블록 그룹들보다 작은 크기는 무시
				if (block_group.total_count > 1)
					store.push_back(block_group);
			}
	if (store.empty())
		return false;
	sort(store.begin(), store.end(), cmp);
	// 선택된 블록그룹을 삭제시키고 점수를 올림
	delete_block_group(store[0]);
	result += (store[0].total_count * store[0].total_count);
	return true;
}
inline void run_gravity() {
	for (int iy = 1, ix, x; iy <= N; ++iy)
		for (ix = N - 1; ix >= 1; --ix)
			if (arr[ix][iy] >= 0) {
				x = ix + 1;
				while (x <= N && arr[x][iy] < -1)
					++x;
				--x;
				if (x != ix)
					swap(arr[ix][iy], arr[x][iy]);
			}
}
inline void turn_blocks() {
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			arr_tmp[ix][iy] = arr[ix][iy];
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			arr[ix][iy] = arr_tmp[iy][N + 1 - ix];
}
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N >> M;
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			cin >> arr[ix][iy];

	result = 0;
	while (true) {
		if (!find_max_block_group())
			break;
		run_gravity();
		turn_blocks();
		run_gravity();
	}
	cout << result << endl;
	return 0;
}
// *&)*@*

1. 역대급으로 시간이 오래 걸렸습니다. (거의 5시간은 넘긴것 같습니다.)
2. 27% SegFault와 39% 시간초과 및 메모리 초과로 상당히 애를 먹었습니다.
3. SegFault는 bfs 내에서 q.front()를 받는 변수가 reference 변수였습니다. 그 뒤 pop에 의해 값이 휘발되어 그런것으로 추측됩니다만, queue의 front 자체가 리턴형이 reference인데 이게 왜 문제가 되는지는 모르겠습니다. (vs에서는 문제되지 않습니다.)
4. 주의해야할 것은 두 가지인 것 같은데, 먼저 블럭 개수가 가장 큰 블럭 그룹이 여러개일 경우, 그중 무지개 블럭의 수가 가장 많고 기준 블럭이 어쩌구 하는 조건입니다. 이 조건을 처음에는 bfs 결과 (결과는 블럭 그룹)를 이중 vector에 담고, 그것들을 반복문 돌려서 찾는 방법으로 하였습니다. 생각해보면 sort의 predicate만 정의해주면 되니 한결 빠르게 동작됩니다.
5. 두번째는 블럭 그룹을 만드는 과정입니다. 처음엔 visit에 기록을 하며 bfs를 끝내고, N X N을 돌리며 visit인 곳일 경우, 블럭 그룹에 추가하는 방식으로 하였으나, bfs를 생성하는 과정에서 이미 상,하,좌,우의 블럭이 어떤 블럭인지 알수 있으므로 바로 추가하면 됩니다.