[BOJ] 상어 중학교 21609

이번 문제는 풀기에 난이도가 좀 높았던 것 같습니다. 아직 구현을 잘 못해서 그런지 시뮬레이션이나 브루트포스 같이  구현 비중이 높은(?) 문제가 나오면 항상 어렵다고 느끼게 되네요. 다른 분들이 푼 것을 참고해서 이해하고 풀어보았습니다.

정리

• 문제를 풀면서 제일 까다로웠던 부분은 블록 그룹을 찾아주는 부분이었습니다. 처음 접근 방식은 bfs로 행, 열 좌표, 블록 그룹과 무지개 블록 개수, 블록 그룹 개수를 찾아주었습니다. 행 열 좌표를 찾으려고 했던 이유는 조건 1번 때문이었는데요. 나중에 생각해보니 왼쪽 위부터 순차적으로 내려오기 때문에 무지개 블록 수와 블록 그룹의 개수가 같다면 마지막 블록 그룹이 저장될 수밖에 없었습니다.
• 일반 블록은 한 번 방문하면 또다시 방문할 수 없지만, 무지개 블록의 경우 여러 번 사용될 수 있기 때문에 매번 초기화해주어야 된다는 부분을 처음에 생각하지 못해 시간을 많이 썼습니다.
• nxn을 다 돌았는데도 블록 그룹이 없다면 while문을 종료하여 답을 출력해주었고, 블록 그룹이 하나라도 있다면 저장해둔 블록 그룹의 개수 x 블록 그룹의 개수를 해주었습니다.
• rotate 코드의 경우 지난번 짠돌이 호석 문제에서 회전과 관련된 문제를 한 번 풀어봐서 그런지 그래도 바로 떠올릴 수 있었습니다.
• 막상 풀고 나니까 생각보다 어려운 느낌은 아닌데 처음에는 코드를 어떤 식으로 짜야할지 감이 잘 안 오는 것 같습니다. 

 

소스코드

#include <iostream>
#include <string.h>
#include <tuple>
#include <queue>

using namespace std;

int n, m, maxsum=0, maxrainbow=0, ans=0;
int arr[21][21];
bool visited[21][21], maxarr[21][21], colorVi[21][21];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

void gravity() {
	for (int i = 0; i < n; i++) {
		int bottom = n - 1; // 4
		for (int j = n-1; j >= 0; j--) {
			if (arr[j][i] == -2) continue;
			else if (arr[j][i] == -1) bottom = j-1;
			else {
				int temp = arr[j][i];
				arr[j][i] = -2;
				arr[bottom--][i] = temp;
				
				
			}
		}
	}
}
void rotate() {
	int temp[21][21];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			temp[i][j] = arr[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			arr[i][j] = temp[j][n - i - 1];
		}
	}
}
tuple<int,int> bfs(int x, int y, int curnum) {
	queue<pair<int, int>> q;
	memset(visited, 0, sizeof(visited));
	visited[x][y] = true;
	colorVi[x][y] = true;
	q.push(make_pair(x, y));
	int sum = 1, rainbow = 0;

	while (!q.empty()){
		int curx = q.front().first;
		int cury = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextx = curx + dx[i];
			int nexty = cury + dy[i];
			if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= n) continue;
			if (visited[nextx][nexty]==false && (arr[nextx][nexty]==0 || arr[nextx][nexty]==curnum)){
				q.push(make_pair(nextx, nexty));
				visited[nextx][nexty] = true;
				if (arr[nextx][nexty] == 0) rainbow++;
				else colorVi[nextx][nexty] = true;
				sum++;
				
			}
		}
	}
	
	return make_tuple(sum, rainbow);
}

bool findBlockGroup() {
	bool flag = false;
	maxsum = 0, maxrainbow = 0;

	memset(maxarr, false, sizeof(maxarr));
	memset(colorVi, false, sizeof(colorVi));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == -2 || arr[i][j] == -1 || arr[i][j] == 0 || colorVi[i][j]==true) continue;
			int blocksum, rainbowsum;
			tie(blocksum, rainbowsum) = bfs(i, j, arr[i][j]);
			if (blocksum < 2) continue;
			if (blocksum >= maxsum) {
				if (maxsum == blocksum && maxrainbow > rainbowsum) continue;
				for (int a = 0; a < n; a++) {
					for (int b = 0; b < n; b++) {
						maxarr[a][b] = visited[a][b];
					}
				}
				maxsum = blocksum;
				maxrainbow = rainbowsum;
				flag = true;
			}
		}
	}

	if (flag == false) return false;

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (maxarr[i][j]) {
				cnt++;
				arr[i][j] = -2;
			}
		}
	}
	ans += cnt*cnt;
	return true;

}
int main(void) {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}

	while (findBlockGroup()) {
		gravity();
		rotate();
		gravity();
	}

	cout << ans << '\n';
}