[BOJ 21609] 상어 중학교 (C++)

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

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

struct blockGroup {
	vector<pair<int, int> > members;
	int num_rainbow;
	pair<int, int> standard_block;
	bool operator<(const blockGroup& b) const {
		if (members.size() == b.members.size()) {
			if (num_rainbow == b.num_rainbow) {
				if (standard_block.first == b.standard_block.first) {
					return standard_block.second > b.standard_block.second;
				}
				return standard_block.first > b.standard_block.first;
			}
			return num_rainbow > b.num_rainbow;
		}
		return members.size() > b.members.size(); 
	}
};

int N, M;
int block[21][21];
bool check[21][21];
vector<blockGroup> groups;
int ans = 0;

void addGroup(int i, int j) {
	int color = block[i][j];
	vector<pair<int, int> > m;
	vector<pair<int, int> > rainbow;
	queue<pair<int, int> > q;
	int num_rainbow = 0;
	m.push_back({ i,j }); q.push({ i,j });
	check[i][j] = true;
	while (!q.empty()) {
		pair<int, int> xy = q.front();
		q.pop();
		for (int k = 0; k < 4; k++) {
			int nx = xy.first + dx[k];
			int ny = xy.second + dy[k];
			if (nx <= 0 || nx > N || ny <= 0 || ny > N)
				continue;
			if (block[nx][ny] == 0 && !check[nx][ny]) {
				check[nx][ny] = true;
				rainbow.push_back({ nx,ny });
				q.push({ nx,ny });
				m.push_back({ nx,ny });
				num_rainbow++;
			}
			if (block[nx][ny] == color && !check[nx][ny]) {
				check[nx][ny] = true;
				q.push({ nx,ny });
				m.push_back({ nx,ny });
			}
		}
	}
	if (m.size() >= 2)
		groups.push_back({ m,num_rainbow,{i,j} });
	for (int i = 0; i < rainbow.size(); i++) {			//다른 group 도 체크 가능하도록 check 표시 풀어줌
		check[rainbow[i].first][rainbow[i].second] = false;
	}
}

bool searchBig() {
	groups.clear();
	memset(check, false, sizeof(check));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (block[i][j] >= 1 && block[i][j] <= M && !check[i][j]) {
				addGroup(i, j);
			}
		}
	}
	if (groups.size() == 0)
		return false;
	sort(groups.begin(), groups.end());
	blockGroup b = groups[0];
	int score = b.members.size();
	ans += (score * score);
	for (int i = 0; i < b.members.size(); i++) {
		int x = b.members[i].first;
		int y = b.members[i].second;
		block[x][y] = M + 1;
	}
	return true;
	//sort groups & pick big group & remove that group
}

void gravity() {
	for (int j = 1; j <= N; j++) {
		for (int i = N-1; i >= 1; i--) {
			if (block[i][j]>=0 && block[i][j]<=M) {
				int row = i + 1;
				bool isMove = false;
				while (row <= N && block[row][j] == M + 1) {
					row++;
					isMove = true;
				}
				block[row - 1][j] = block[i][j];
				if (isMove) 
					block[i][j] = M + 1;
			}
		}
	}
}

void rotate() {
	vector<vector<int> > v(N+1);
	for (int i = 1; i <= N; i++) {				
		for (int j = N; j >= 1; j--) {
			v[i].push_back(block[i][j]);
		}
	}
	for (int j = 1; j <= N; j++) {
		for (int i = 1; i <= N; i++) {
			block[i][j] = v[j][i-1];
		}
	}
}


int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> block[i][j];
		}
	}
	while (searchBig()) {
		gravity();
		rotate();
		gravity();
	}
	cout << ans << "\n";
	return 0;

}

오늘의 교훈: "문제를 잘읽자"

탐색(BFS)+구현 문제.

 

여기서 같은 블록 그룹이 되는 기준은 "임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다" && "일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다". 이다.

즉, 무지개 블록은 인접한 칸으로 이동해서 다른 모든 칸으로 이동할 수 있다면 그룹 간 공유 가능하다.

 

즉, 무지개 블록은 공유 가능한 요소이므로, BFS 탐색할 때 visit 표시 해주고, 다른 그룹을 다시 탐색하러 갈 때 무지개 블록에 visit 표시해 준 것을 풀어줘서 다른 그룹도 그 무지개 블록을 탐색 가능하게 만들어준다.