(백준 c++)23290 마법사 상어와 복제

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

23290번: 마법사 상어와 복제

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define PAIR pair<pair<int, int>, int>

using namespace std;

int S;
int sharkX;
int sharkY;
int sx[4] = {-1, 0, 1, 0};
int sy[4] = {0, -1, 0, 1};
int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
vector<string> combinations;
vector<vector<vector<PAIR>>> board(4, vector<vector<PAIR>>(4));
vector<vector<vector<PAIR>>> newBoard(4, vector<vector<PAIR>>(4));
vector<vector<int>> smell(4, vector<int>(4, 0));
queue<PAIR> fishes;
queue<PAIR> copiedFishes;

void getCombinations(int index, int count, string current){
	if(count == 3){
		combinations.push_back(current);
		return;
	}
	
	for(int i = 0; i < 4; i++){
		current += to_string(i);
		getCombinations(i, count + 1, current);
		current.pop_back();
	}
}

bool checkRange(int x, int y) {
	if(x >= 0 && x < 4 && y >= 0 && y < 4){
		return true;
	}
	
	return false;
}

void input() {
	int M;
	
	cin >> M >> S;
	
	for(int i = 0; i < M; i++){
		int x, y, d;
		
		cin >> x >> y >> d;
		
		fishes.push({{x - 1, y - 1}, d - 1});
	}
	
	cin >> sharkX >> sharkY;
	
	sharkX--;
	sharkY--;
}

void copy() {
	board = newBoard;
	copiedFishes = fishes;
}

void moveFishes() {
	int size = fishes.size();
	
	while(size--){
		int x = fishes.front().first.first;
		int y = fishes.front().first.second;
		int direct = fishes.front().second;
		bool isMoved = false;
		
		fishes.pop();
		
		for(int i = 0; i < 8; i++){
			int nx = x + dx[direct];
			int ny = y + dy[direct];
			
			if(checkRange(nx, ny) && !smell[nx][ny] && !(nx == sharkX && ny == sharkY)){
				isMoved = true;
				fishes.push({{nx, ny}, direct});
				
				break;
			}
			
			direct = direct - 1 >= 0 ? direct - 1 : 7;
		}
		
		if(!isMoved){
			fishes.push({{x, y}, direct});
		}
	}
}

void moveShark() {
	int highestAteFishes = 0;
	int nextX, nextY;
	bool isChanged = false;
	vector<vector<vector<PAIR>>> copiedBoard(4, vector<vector<PAIR>>(4));
	vector<vector<vector<PAIR>>> newBoard(4, vector<vector<PAIR>>(4));
	vector<vector<int>> copiedSmell(4, vector<int>(4, 0));
	vector<vector<int>> newSmell(4, vector<int>(4, 0));
	vector<pair<int, int>> noAte;
	
	while(!fishes.empty()){
		int x = fishes.front().first.first;
		int y = fishes.front().first.second;
		int d = fishes.front().second;
		
		fishes.pop();
		
		board[x][y].push_back({{x, y}, d});
	}
	
	for(int i = 0; i < combinations.size(); i++){
		int copiedX = sharkX;
		int copiedY = sharkY;
		int ateFishes = 0;
		bool isPossible = true;
		
		copiedBoard = board;
		copiedSmell = smell;
		
		for(int j = 0; j < 3; j++){
			int direct = combinations[i][j] - '0';
			
			copiedX += sx[direct];
			copiedY += sy[direct];
			
			if(!checkRange(copiedX, copiedY)){
				isPossible = false;
				break;
			}
			
			if(copiedBoard[copiedX][copiedY].size()){
				ateFishes += copiedBoard[copiedX][copiedY].size();
				copiedBoard[copiedX][copiedY].clear();
				copiedSmell[copiedX][copiedY] = 3;
			}
		}
		
		if(isPossible){
			if(highestAteFishes < ateFishes){
				nextX = copiedX;
				nextY = copiedY;
				highestAteFishes = ateFishes;
				newBoard = copiedBoard;
				newSmell = copiedSmell;
				isChanged = true;
			} else if(ateFishes == 0){
				noAte.push_back({copiedX, copiedY});
			}
		}
	}
	
	if(isChanged){
		sharkX = nextX;
		sharkY = nextY;
		board = newBoard;
		smell = newSmell;
	} else{
		sharkX = noAte.front().first;
		sharkY = noAte.front().second;
	}
}

void eraseSmell() {
	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 4; j++){
			if(smell[i][j]){
				smell[i][j]--;
			}
		}
	}
}

void copyMagic() {
	fishes = copiedFishes;
	
	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 4; j++){
			for(int k = 0; k < board[i][j].size(); k++){
				fishes.push(board[i][j][k]);
			}
		}
	}
}

void countFishes() {
	cout << fishes.size();
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
	
	input();
	
	getCombinations(0, 0, "");
	
	while(S--){
		copy();
		
		moveFishes();
		
		moveShark();
		
		eraseSmell();
		
		copyMagic();
	}
	
	countFishes();
	
	return 0;
}