백준 - 마법사 상어와 복제 (23290) [C++]

 이 문제는 구현, 시뮬레이션 문제이다. 문제 길이는 짧아보이지만 생각보다 어려운 문제였다.

 

 이 문제에서 핵심은 물고기들, 상어, 물고기 냄새를 따로 저장하여 구현하는 것이다. 처음에 물고기들과 상어를 같이 넣어놓고 erase를 통해 빼면서 구현했는데, 테스트 케이스에서조차 2초 안에 답이 나오지 않는다. 이는 erase가 내부적으로 O(N) 시간이 걸리기 때문이었다. erase 함수는 되도록 그냥 사용하지 않아야겠다는 생각이 문제를 풀 수록 든다.

 

 또한 빠뜨리기 쉬운 부분은 물고기의 방향을 찾을 때, 입력에서 주어지는 LEFT부터 시계 방향과 다르게 반시계 방향으로 탐색해야 한다. 이 부분을 까먹어 처음에 전혀 다른 방향으로 답이 나왔었다. 

 

 위 두 가지 이외에도 구현이 쉽지는 않지만, 삼성 기출 문제를 몇 문제 풀어보면 익숙한 패턴이라는 사실을 알 수 있다. 개인적인 느낌으로 삼성 문제는 보통 동시에 이벤트가 발생하는 경우가 많은데, 이를 해결하는 가장 좋은 방법은 복사본을 처음에 만들어놓고 변화를 체크한 다음 일괄적으로 처리하면 보통 오류가 없다.

 또한 이 문제에서와 같이 만약 상어, 물고기, 냄새 등 다양한 객체가 존재할 때 하나의 자료 구조에 모두 집어넣는 것이 아니라 따로 분리해서 각각을 위한 자료 구조로 만들어준다면 훨씬 구현이 수월했다.

 

 

 

#include <iostream>
#include <vector>

using namespace std;

#define LEFT 0
#define UPLEFT 1
#define UP 2
#define UPRIGHT 3
#define RIGHT 4
#define DOWNRIGHT 5
#define DOWN 6
#define DOWNLEFT 7

#define SHARK 0
#define FISH 1

struct node {
	int status;
	int direction;
};

struct shark {
	int y;
	int x;
};

vector<node> matrix[5][5];
int smell[5][5];
int M, S;
shark shrk;

bool inRange(int y, int x) {
	if (1 <= y && y <= 4 && 1 <= x && x <= 4) {
		return true;
	}
	return false;
}

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

void fishMove() {
	vector<node> temp[5][5];

	for (int y = 1; y <= 4; y++) {
		for (int x = 1; x <= 4; x++) {
			
			for (node &present : matrix[y][x]) {
				if (present.status == FISH) {
					int direction = present.direction;
					bool allFlag = false;

					for (int i = 0; i < 8; i++) {
						int nextDirect = (direction - i) % 8;

						if (nextDirect < 0) {
							nextDirect += 8;
						}
						int ny = y + dy[nextDirect];
						int nx = x + dx[nextDirect];

						if (inRange(ny, nx) && smell[ny][nx] == 0) {	// inRange, smell check
							
							if (shrk.y == ny && shrk.x == nx) {
								continue;
							}
						
							allFlag = true;
							temp[ny][nx].push_back({ FISH, nextDirect });
							break;
							
						}
					}

					if (!allFlag) {
						temp[y][x].push_back({ FISH, direction });
					}
				}
			}
		}
	}

	for (int y = 1; y <= 4; y++) {
		for (int x = 1; x <= 4; x++) {
			matrix[y][x] = temp[y][x];
		}
	}
}

int sdy[] = { -1, 0, 1, 0 };
int sdx[] = { 0, -1, 0, 1 };
string result;
int maxFish;

void process(int y, int x, string str, int acc, vector<vector<vector<node>>> tempMatrix) {
	if (str.size() == 3) {
		if (acc > maxFish) {
			maxFish = acc;
			result = str;
		}
		return;
	}

	for (int d = 0; d < 4; d++) {
		int ny = y + sdy[d];
		int nx = x + sdx[d];

		if (inRange(ny, nx)) {
			vector<node> temp = tempMatrix[ny][nx];
			
			tempMatrix[ny][nx].clear();
			
			process(ny, nx, str + (char)('0' + d), acc + temp.size(), tempMatrix);

			tempMatrix[ny][nx] = temp;
		}
	}
}

vector<vector<bool>> sharkMove() {
	vector<vector<bool>> smellResult(5, vector<bool>(5, false));
	int sy = shrk.y, sx = shrk.x;

	vector<vector<vector<node>>> tempMatrix(5, vector<vector<node>>(5, vector<node>()));

	for (int y = 1; y <= 4; y++) {
		for (int x = 1; x <= 4; x++) {
			tempMatrix[y][x] = matrix[y][x];
		}
	}

	// find max
	result = "";
	maxFish = -1;
	process(sy, sx, "", 0, tempMatrix);
	int ny = sy, nx = sx;

	for (char c : result) {
		int num = c - '0';
		
		ny = ny + sdy[num];
		nx = nx + sdx[num];

		if (!matrix[ny][nx].empty()) {
			smellResult[ny][nx] = true;
			smell[ny][nx] = 2;
			matrix[ny][nx].clear();
		}
	}

	shrk.y = ny;
	shrk.x = nx;

	return smellResult;
}

void print() {
	for (int y = 1; y <= 4; y++) {
		for (int x = 1; x <= 4; x++) {
			cout << matrix[y][x].size() << " ";
		}
		cout << '\n';
	}
	cout << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> M >> S;

	for (int i = 0; i < M; i++) {
		int fx, fy, d;

		cin >> fx >> fy >> d;
		d--;
		matrix[fx][fy].push_back({ FISH, d });
	}

	int sx, sy;
	cin >> sx >> sy;
	shrk = { sx, sy };

	for (int i = 0; i < S; i++) {
		// 1. replicate(not complete)
		vector<node> copy[5][5];
		for (int y = 1; y <= 4; y++) {
			for (int x = 1; x <= 4; x++) {
				copy[y][x] = matrix[y][x];
			}
		}

		// 2. fish move
		fishMove();

		// 3. shark move
		vector<vector<bool>> tempSmell = sharkMove();

		// 4. smell decrement
		for (int y = 1; y <= 4; y++) {
			for (int x = 1; x <= 4; x++) {
				if (!tempSmell[y][x] && smell[y][x] > 0) {
					smell[y][x]--;
				}
			}
		}

		// 5. replication complete
		for (int y = 1; y <= 4; y++) {
			for (int x = 1; x <= 4; x++) {
				for (node &temp : copy[y][x]) {
					matrix[y][x].push_back(temp);
				}
			}
		}
	}

	int answer = 0;

	for (int y = 1; y <= 4; y++) {
		for (int x = 1; x <= 4; x++) {
			answer += matrix[y][x].size();
		}
	}

	cout << answer << '\n';

	return 0;
}