백준 - 마법사 상어와 복제 (23290번)

백준 - 마법사 상어와 복제 (23290번)

주어진데로 그냥 구현하면 되는데, 물고기들을 queue를 써서 관리했다.

map이 넓지 않아서 그냥 3차원 배열을 벡터 느낌으로 관리하거나 2차원 배열의 자료형을 벡터로 관리하는 것이 더 효율적이었을 것 같다.

큐로 관리하니까 pop, push가 불필요하게 많이 되고 있어서 속도는 좀 느렸다.
빠른 코드들은 그냥 배열로 관리하는 듯.

sort의 copmare 함수를 구현하면서 invalid compare 버그를 만났는데, 이전에도 몇번 만났는데 대충대충 고쳐왔다.
이번에 좀 찾아봤는데, sort의 compare함수는 strick weak ordering을 만족해야 한다.

strict-weak-ordering 참고 링크를 참고했다.

아마 나머지 세 조건보다 1번 조건을 만족하지 못해서 버그가 발생하기 쉬울 것이라 생각된다.
간단하게 이해하자면 a는 a보다 클수없다 를 항상 만족하도록 compare를 짜는게 중요하다.

아래와 같이 오름차순을 만들고 싶은 compare 함수를 작성했다고 하자.

bool compare (int a, int b) {
	if (a > b)
    	return false;
    return true;
}

해당 함수에 compare(a, a)를 하면 true가 나오는데, 이는 strict-weak-ordering을 위배한다.
따라서 a는 a보다 크면 안된다 는 조건을 맞춰서 다음과 같이 compare 함수를 작성해야 한다.

bool compare (int a, int b) {
	if (a >= b)
    	return false;
    return true;
}

작성한 코드는 다음과 같다.

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

using namespace std;

int m, s;
int fishRowDir[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int fishColDir[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };

int sharkRowDir[5] = { 0, -1, 0, 1, 0 };
int sharkColDir[5] = { 0, 0, -1, 0, 1 };

typedef struct __fish {
	int row;
	int col;
	int dir;
}fish;

typedef struct __fish_num_info {
	int num;
	int move[3];
}fish_num_info;

int smell_map[5][5];

bool comp(const fish_num_info &a, const fish_num_info &b)
{
	if (a.num != b.num)
		return a.num > b.num;
	else {
		if (a.move[0] == b.move[0]) {
			if (a.move[1] == b.move[1])
				return a.move[2] < b.move[2];
			else
				return a.move[1] < b.move[1];
		}
		return a.move[0] < b.move[0];	
	}
}
int main(void)
{
	cin >> m >> s;
	queue<fish> q;
	fish f;
	for (int i = 0; i < m; i++) {
		cin >> f.row >> f.col >> f.dir;
		q.push(f);
	}
	fish shark;
	cin >> shark.row >> shark.col;

	for (int i = 1; i < 5; i++)
		for (int j = 1; j < 5; j++)
			smell_map[i][j] = -1;

	for (int iter = 0; iter < s; iter++) {
		// 매 단계에서 3단계에서 쓰기 위해서 row, col 별 fish 갯수를 count할 map 선언
		int fish_count_map[5][5];
		for (int i = 1; i < 5; i++)
			for (int j = 1; j < 5; j++)
				fish_count_map[i][j] = 0;

		// 1단계 복제를 위해 미리 Queue Copy
		queue<fish> copied(q);

		// 2단계 물고기가 한 칸 이동
		int size = q.size();
		for (int s = 0; s < size; s++) {
			fish f = q.front(); q.pop();
			int nrow, ncol, ndir;
			bool is_move = false;
			for (int i = 0; i < 8; i++) {
				ndir = (f.dir - i) % 9;
				if (ndir <= 0)
					ndir += 8;
				nrow = f.row + fishRowDir[ndir];
				ncol = f.col + fishColDir[ndir];

				// 상어가 있는 칸
				if (nrow == shark.row && ncol == shark.col)
					continue;

				// 물고기 냄새가 있는 곳
				if (smell_map[nrow][ncol] != -1)
					continue;

				// 격자를 벗어나는 칸
				if (nrow < 1 || nrow > 4 || ncol < 1 || ncol > 4)
					continue;

				// 이동할 곳이 존재해서 이동을 함.
				is_move = true;
				fish new_f = { nrow, ncol, ndir };
				q.push(new_f);
				fish_count_map[nrow][ncol]++;
				break;
			}

			// 이동할 곳이 존재하지 않는다면, 이동하지 않으므로 다시 큐에 넣어줘야 함.
			if (!is_move) {
				q.push(f);
				fish_count_map[f.row][f.col]++;
			}
		}
		// 3단계 상어를 이동시킴
		// 상어가 진행할 수 있는 경로에 물고기가 몇마리 잇는지 체크
		int nrow, ncol, ndir;
		vector<fish_num_info> candidate;
		for (int i = 1; i < 5; i++) {
			for (int j = 1; j < 5; j++) {
				for (int k = 1; k < 5; k++) {
					int num = 0;
					vector<fish> visit;
					nrow = shark.row + sharkRowDir[i];
					ncol = shark.col + sharkColDir[i];
					if (nrow < 1 || nrow > 4 || ncol < 1 || ncol > 4)
						continue;
					visit.push_back({ nrow, ncol, fish_count_map[nrow][ncol]});

					nrow = nrow + sharkRowDir[j];
					ncol = ncol + sharkColDir[j];
					if (nrow < 1 || nrow > 4 || ncol < 1 || ncol > 4)
						continue;
					if(visit[0].row != nrow || visit[0].col != ncol)
						visit.push_back({ nrow, ncol, fish_count_map[nrow][ncol] });
					
					nrow = nrow + sharkRowDir[k];
					ncol = ncol + sharkColDir[k];
					if (nrow < 1 || nrow > 4 || ncol < 1 || ncol > 4)
						continue;
					bool is_exist = false;
					for (int s = 0; s < visit.size(); s++)
						if (visit[s].row == nrow && visit[s].col == ncol) {
							is_exist = true;
							break;	
						}
					if(!is_exist)
						visit.push_back({ nrow, ncol, fish_count_map[nrow][ncol] });

					for (int s = 0; s < visit.size(); s++)
						num += visit[s].dir;

					fish_num_info fn_info;
					fn_info.num = num;
					fn_info.move[0] = i;
					fn_info.move[1] = j;
					fn_info.move[2] = k;
					candidate.push_back(fn_info);
				}
			}
		}
		// 가장 물고기 개수가 많았던 이동을 찾음
		sort(candidate.begin(), candidate.end(), comp);
		fish_num_info max_move = candidate[0];
		fish shark_move_info[3];

		// 상어 위치를 업데이트
		for (int i = 0; i < 3; i++) {
			shark.row = shark.row + sharkRowDir[max_move.move[i]];
			shark.col = shark.col + sharkColDir[max_move.move[i]];
			shark_move_info[i].row = shark.row;
			shark_move_info[i].col = shark.col;
		}

		// 이동 위치에 존재하는 물고기들을 지우고, 냄새를 새김
		size = q.size();
		for (int s = 0; s < size; s++) {
			fish f = q.front(); q.pop();
			bool is_contain = false;
			for (int i = 0; i < 3; i++) {
				if (f.row == shark_move_info[i].row && f.col == shark_move_info[i].col) {
					is_contain = true;	
					break;
				}
			}
			if (is_contain) 
				smell_map[f.row][f.col] = iter;
			else 
				q.push(f);
			
		}
		
		// 4단계 두 단계 전 연습에서 생긴 물고기의 냄새를 격자에서 지움
		for (int i = 1; i < 5; i++) {
			for (int j = 1; j < 5; j++) {
				if (smell_map[i][j] == -1)
					continue;
				// 만약 두 단계 전에 생긴 냄새라면 지워줌
				if (smell_map[i][j] == iter - 2)
					smell_map[i][j] = -1;
			}
		}

		// 5단계 미리 카피해둔 상어들을 복제함
		while (1) {
			if (copied.empty())
				break;
			fish f = copied.front(); copied.pop();
			q.push(f);
		}
	}

	cout << q.size() << "\n";

	return 0;
}