백준 c++ 21609 "상어 중학교" -[PlusUltraCode]

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

21609번: 상어 중학교

 

[필자 사고]

BFS 구현문제다.

조건들이 어마무시해서 한글자라도 잘못 읽으면 골로가는 문제다.

중요 조건들은 독자들이 잘 읽기를 바라며 이 문제에서 챙겨야 되는 핵심 개념들을 공부해 보겠다.

 

먼저 vector를 이용한 정렬 시스템 정의다.

 

bool cmp(Node a , Node b){

 

} 

 

형태로 작성된다.

 

return true 형태로 작성하면 a 랑 b 형태로 순서가 되고

return false 형태로 작성하면 b a 형태로 순서가 설정된다.

 

또한 return a.size<b.size 형태로 작성하면 a b 순서로 원하는대로 설정할 수 있따.

 

그리고 이 문제의 핵심은 visted를 사용할 시 0인 무지개 블록을 방문했을 때는 따로 false 를 통해 방문처리를 건드려 줘야된다.

 

그리고 이 문제에서 필자가 계속 골머리 썩인거는

행과 열의 문제다.

 

필자는 문제에서 행이 작다는 의미가 garo인덱스가 작다는 의미로 착각했따. 

 

실제로는 행이 작다는 의미는 sero가 작은값이다. 조심하자.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
using namespace std;
int N, M;
int Result = 0;
vector<vector<int>> Arr;
typedef pair<int, int> Node;
typedef struct group {
	vector<Node> index;
	int groupSize;
	int mujiCount;
};

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

void Input() {
	cin >> N >> M;
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> Arr[i][k];
		}
	}
}

void Gravity() {
	for (int k = 0; k < N; k++) {
		queue<int> myQueue;
		for (int i = N - 1; i >= 0; i--) {
			//빈칸인경우
			//-1인경우
			//자연수인경우

			if (Arr[i][k] == -2) {
				myQueue.push(i);
			}
			else if (Arr[i][k] >= 0) {
				if (myQueue.empty() == false) {
					int binkan = myQueue.front();
					myQueue.pop();
					Arr[binkan][k] = Arr[i][k];
					Arr[i][k] = -2;
					myQueue.push(i);
				}
			}
			else if (Arr[i][k] == -1) {
				while (!myQueue.empty()) {
					myQueue.pop();
				}
			}

		}
		while (!myQueue.empty()) {
			myQueue.pop();
		}
	}
}
void Rotate() {
	vector<vector<int>> Arr2;
	Arr2 = Arr;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			Arr2[N - 1 - k][i] = Arr[i][k];
		}
	}
	Arr = Arr2;
}
void Print() {
	cout << '\n';
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (Arr[i][k] == -2) {
				cout << "  ";
			}
			else if (Arr[i][k] < 0) {
				cout << Arr[i][k] << " ";
			}
			else cout << Arr[i][k] << " ";
		}
		cout << '\n';
	}
	cout << '\n';
}

vector<vector<bool>> visited;
vector<group> Group;
bool gijunSort(Node a, Node b) {
	//무지개 블록이 아니고
	// 행의 번호가 가장 작아야되고
	// 그것도 같다면 열의 번호가 가장 작은거
	if (Arr[a.first][a.second] == 0) {
		return false; // a만 0이므로 b를 먼저 배치
	}
	if (Arr[b.first][b.second] == 0) {
		return true; // b만 0이므로 a를 먼저 배치
	}


	if (a.first == b.first) {
		return a.second < b.second;
	}
	return a.first < b.first;

}

void BFS(int sero, int garo) {
	queue<Node> myQueue;
	myQueue.push({ sero,garo });
	visited[sero][garo] = true;
	vector<Node> zeroTank;
	vector<Node> indexTank;
	indexTank.push_back({ sero,garo });
	int colorNumber = Arr[sero][garo];
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();

		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) == false)continue;
			if (visited[nextSero][nextGaro] == true)continue;
			if (Arr[nextSero][nextGaro] == 0) {
				zeroTank.push_back({ nextSero,nextGaro });
				indexTank.push_back({ nextSero,nextGaro });
				myQueue.push({ nextSero,nextGaro });
				visited[nextSero][nextGaro] = true;
			}
			else if (Arr[nextSero][nextGaro] == colorNumber) {
				indexTank.push_back({ nextSero,nextGaro });
				myQueue.push({ nextSero,nextGaro });
				visited[nextSero][nextGaro] = true;
			}
		}
	}
	if (indexTank.size() != 1) {
		int size = indexTank.size();
		int mujisize = zeroTank.size();
		sort(indexTank.begin(), indexTank.end(), gijunSort);
		Group.push_back({ indexTank,size,mujisize });
	}
	for (int i = 0; i < zeroTank.size(); i++) {
		int sero = zeroTank[i].first;
		int garo = zeroTank[i].second;
		visited[sero][garo] = false;

	}


}

bool deleteSort(group a, group b) {
	//클수록
	//같으면 무지개가 많을수록
	//같으면 행이 클수록
	//같으면 열이 클수록
	if (a.groupSize == b.groupSize && a.mujiCount == b.mujiCount &&
		a.index[0].first == b.index[0].first) {
		return a.index[0].second > b.index[0].second;
	}
	if (a.groupSize == b.groupSize && a.mujiCount == b.mujiCount) {
		return a.index[0].first > b.index[0].first;
	}
	if (a.groupSize == b.groupSize) {
		return a.mujiCount > b.mujiCount;
	}
	return a.groupSize > b.groupSize;
}


void GameStart() {
	Group.clear();
	visited.clear();
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(N, false);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (Arr[i][k] <= 0)continue;
			if (visited[i][k] == false) {
				BFS(i, k);
			}
		}
	}
	sort(Group.begin(), Group.end(), deleteSort);
}

void DeleteGroup() {
	int count = 0;
	for (int i = 0; i < Group[0].index.size(); i++) {
		int sero = Group[0].index[i].first;
		int garo = Group[0].index[i].second;
		count++;
		Arr[sero][garo] = -2;
	}
	Result += count * count;
	
}


int main(void) {
	Input();
	
	while (1) {
		GameStart();

		if (Group.size() == 0) {
			cout << Result;
			return 0;
		}
		DeleteGroup();
	
		Gravity();
	
		Rotate();
	
		Gravity();
		
	}
}