백준 - 상어 중학교 (21609) [C++]

 이 문제는 시뮬레이션 문제이고, bfs를 활용하여 풀었다. 이 문제에서 가장 어려운 부분은 첫 번째로 블록 그룹을 찾아내는 것이고, 두 번째는 중력 작용을 시키는 것이다. 

 

 첫 번째는 bfs를 이용하였는데, node라는 구조체를 만들어 필요한 정보들을 넣도록 하였고, 이를 bfs에서 리턴하도록 했다. 주의할 점은 격자에서 무지개 블록, 즉 0은 visited에 포함되면 안된다. 그러나 bfs 내부에서 0에 대한 visited를 처리하지 않으면 당연히 무한 루프에 걸리게 된다. 이를 해결하기 위해서 일단 bfs를 수행하고, bfs가 끝난 뒤 무지개 블록에 대해 visited가 true가 되어있는 걸 false로 바꿔주면 된다.

 상하좌우가 중요하지 않다는 점도 중요한 포인트이다. 임의의 (y, x)에 대해 같은 그룹에 속하면서 y,x보다 행이 작은 부분이 visited = true 가 되어있을 가능성은 없기 때문이다. 만약 그런 점이 있다면 애초에 같은 그룹이 될 수 없다. 단지 visited를 bfs가 끝나도 유지시켜주면서, false인 점만을 bfs 시작점으로 잡으면 해결된다.

 

 

 두 번째는 중력에 의해 떨어지는 부분인데, 이는 top이라는 변수와 swap을 통해 간단히 구현할 수 있다. y를 맨 아래에서 시작하면서, 만약 DISABLE된 격자이면 넘어가고, 검은색 블록이면 중력에 넘어가지 않으므로 y - 1을 top에 갱신시켜준다. 만약 격자의 숫자가 0보다 크거나 같다면, 즉 무지개 블록이거나 일반 블록이면 중력의 작용을 받으므로 top과 swap을 해주면 된다.

 

위 두 가지 사항을 문제없이 구현한다면 쉽게 풀 수 있는 문제이다.

 

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

using namespace std;

#define DISABLE -100

int N, M;

vector<vector<int>> matrix;
vector<vector<bool>> visited;

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

bool inRange(int y, int x) {
	if (0 <= y && y < N && 0 <= x && x < N) {
		return true;
	}
	return false;
}

struct node {
	int cnt;
	int rainbow;
	vector<pair<int, int>> blocks;
};

node bfs(int startY, int startX) {
	int blockNum = matrix[startY][startX];
	
	node result = { 1, 0, vector<pair<int, int>>() };
	result.blocks.push_back({ startY, startX });

	queue<pair<int, int>> q;
	visited[startY][startX] = true;
	q.push({ startY, startX });

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

		if (matrix[present.first][present.second] == 0) {
			(result.rainbow)++;
		}

		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] &&
				(matrix[ny][nx] == 0 || matrix[ny][nx] == blockNum)) {
				result.cnt++;
				result.blocks.push_back({ ny, nx });
				visited[ny][nx] = true;
				q.push({ ny, nx });
			}
		}
	}

	return result;
}

void down() {
	for (int x = 0; x < N; x++) {
		int top = N - 1;

		for (int y = N - 1; y >= 0; y--) {
			int present = matrix[y][x];

			if (present == DISABLE) {
				continue;
			}
			else if (present >= 0) {
				swap(matrix[top][x], matrix[y][x]);
				top--;
			}
			else if (present == -1) {
				top = y - 1;
			}
		}
	}
}

void roll() {
	vector<vector<int>> result;

	for (int x = N - 1; x >= 0; x--) {
		vector<int> temp;

		for (int y = 0; y < N; y++) {
			temp.push_back(matrix[y][x]);
		}

		result.push_back(temp);
	}

	matrix = result;
}

void print() {
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (matrix[y][x] == DISABLE) {
				cout << 'D' << " ";
				continue;
			}
			cout << matrix[y][x] << " ";
		}
		cout << '\n';
	}
	cout << '\n';
}

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

	cin >> N >> M;

	matrix = vector<vector<int>>(N, vector<int>(N));

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

	long long answer = 0;

	while (true) {
		// 1. find block group
		node result = { -1, -1, vector<pair<int, int>>() };

		visited = vector<vector<bool>>(N, vector<bool>(N, 0));
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (matrix[y][x] > 0 && !visited[y][x]) {
					node temp = bfs(y, x);

					if (temp.cnt == 1) {
						visited[y][x] = false;
						continue;
					}

					if (temp.cnt > result.cnt) {
						result = temp;
					}
					else if (temp.cnt == result.cnt) {
						if (temp.rainbow >= result.rainbow) {
							result = temp;
						}
					}

					for (pair<int, int> &r : temp.blocks) {
						if (matrix[r.first][r.second] == 0) {
							visited[r.first][r.second] = false;
						}
					}
				}
			}
		}

		// no block group
		if (result.cnt == -1) {
			break;
		}

		// 2. remove block group
		answer += result.cnt * result.cnt;

		for (pair<int, int>& r : result.blocks) {
			matrix[r.first][r.second] = DISABLE;
		}

		// 3. down
		down();

		// 4. roll
		roll();

		// 5. down
		down();
	}

	cout << answer << '\n';

	return 0;
}