21609번 상어 중학교

오.... BFS할때 check배열을 가볍게 생각했었는데 중복개념이 들어가니까 디버그를 찾는데 엄청 시간이 걸렸다..
결국 2시간 반만에 해결!

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

using namespace std;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int n, m;
int map[21][21];
int ch[21][21];
int ch2[21][21];
int ch3[21][21];
int ans = 0;
struct Loc {
	int cnt, rain, x, y;
	Loc(int a, int b, int c, int d) {
		cnt = a;
		rain = b;
		x = c;
		y = d;
	}
	bool operator<(const Loc& b) const {
		if (cnt != b.cnt) return cnt < b.cnt;
		if (rain != b.rain) return rain < b.rain;
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
};
void go() {
	int len = n / 2;
	for (int k = 0; k < len; k++) {
		int start_x = 0 + k;
		int start_y = 0 + k;
		int end_x = 0 + n - k - 1;
		int end_y = 0 + n - k - 1;
		int idx_x = start_x;
		int idx_y = start_y;
		int cnt = 0;
		vector<int> tmp;
		for (int i = end_x; i > start_x; i--) tmp.push_back(map[i][start_y]);
		for (int i = end_x; i > start_x; i--) map[i][start_y] = map[start_x][idx_y++];
		for (int i = start_y; i < end_y; i++) map[start_x][i] = map[idx_x++][end_y];
		for (int i = start_x; i < end_x; i++) map[i][end_y] = map[end_x][idx_y--];
		for (int i = end_y; i > start_y; i--) map[end_x][i] = tmp[cnt++];
	}

}
void gravity() {
	for (int j = 0; j < n; j++) {
		//모든 행
		while (1) {
			bool ok = true;
			for (int i = n - 1; i >= 1; i--) {
				if (map[i][j] == -2) {
					if (map[i - 1][j] >= 0) {
						map[i][j] = map[i - 1][j];
						map[i - 1][j] = -2;
						ok = false;
					}
				}
			}
			if (ok) break;
		}
	}
}
int main() {
	//freopen("in1.txt", "rt",stdin);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	int tmp2 = 1;
	while (1) {
		//ch배열 초기화
		for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ch[i][j] = 0;
		for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ch2[i][j] = 0;
		priority_queue<Loc> pQ;
		queue<pair<int, int> > Q;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 0 || map[i][j] == -1 || map[i][j] == -2) continue;
				for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ch3[i][j] = 0;
				ch[i][j] = 1;
				int same = map[i][j];
				int rainbow = 0;
				int cnt = 1;
				Q.push(make_pair(i, j));
				while (!Q.empty()) {
					int x, y;
					tie(x, y) = Q.front(); Q.pop();
					for (int k = 0; k < 4; k++) {
						int xx = x + dx[k];
						int yy = y + dy[k];
						if (xx >= n || xx < 0 || yy >= n || yy < 0) continue;
						if (map[xx][yy] == -1 || map[xx][yy] == -2) continue;
						if (map[xx][yy] == same) {
							if (ch[xx][yy] == 0) {
								ch[xx][yy] = 1;
								cnt++;
								Q.push(make_pair(xx, yy));
							}
						}
						else if (map[xx][yy] == 0) {
							if (ch3[xx][yy] == 0) {
								ch3[xx][yy] = 1;
								cnt++;
								Q.push(make_pair(xx, yy));
								rainbow++;
							}
						}
					}
				}
				if (cnt <= 1) continue;
				else if (cnt >= 2) {
					pQ.push(Loc(cnt, rainbow, i, j));
				}
			}
		}
		int tmp3 = pQ.size();
		if (tmp3 == 0) {
			break;
		}
		int a = 0, b = 0, x1 = 0, y1 = 0;
		a = pQ.top().cnt;
		x1 = pQ.top().x;
		y1 = pQ.top().y;
		ans += a * a;
		queue<pair<int, int> > sQ;
		ch2[x1][y1] = 1;
		int same = map[x1][y1];
		map[x1][y1] = -2;
		sQ.push(make_pair(x1, y1));
		while (!sQ.empty()) {
			int x2, y2;
			tie(x2, y2) = sQ.front(); sQ.pop();
			for (int k = 0; k < 4; k++) {
				int xx = x2 + dx[k];
				int yy = y2 + dy[k];
				if (xx >= n || xx < 0 || yy >= n || yy < 0) continue;
				if (map[xx][yy] == -2 || map[xx][yy] == -1) continue;
				if (map[xx][yy] == 0 || map[xx][yy] == same) {
					if (ch2[xx][yy] == 0) {
						ch2[xx][yy] = 1;
						map[xx][yy] = -2;
						sQ.push(make_pair(xx, yy));
					}
				}
			}
		}
		//이제 중력단계
		gravity();
		//이제 90도 반시계
		go();
		gravity();
	}

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