[C++] 백준 23290번 마법사 상어와 복제

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

23290번: 마법사 상어와 복제

삼성 SW 역량 테스트 기출 문제 수록 문제

고려해야 할 부분들이 상당히 많은 문제이지만, 특별한 알고리즘은 필요가 없다.

 

문제 조건 정리

기본 조건

1. 4x4 격자
2. r행 c열을 (r, c)로 표현
3. 물고기 M마리가 주어지고, 이동 방향(8가지)을 가진다.
4. 상어도 격자 한 칸에 위치한다.
5. 최초에는 둘 이상의 물고기가 같은 칸에 있을 수 있고, 상어와 물고기가 같은 칸에 있을 수 있다.

상어가 마법을 시전하면 아래와 같은 순서가 진행된다.

1. 복제를 시전한다. 바로 되는 게 아니라 (5)에서 복제가 된다.
2. 물고기들이 방향에 따라 한 칸 이동한다. 이 때 다음과 같은 칸으로는 이동할 수 없다.
   - 상어가 있는 칸
   - 물고기 냄새가 남아있는 칸
   - 범위를 벗어나는 칸
   이동 가능한 칸이 나올 때까지 방향을 45도 반시계로 회전하면서 찾고, 없을 경우에는 이동하지 않는다.
3. 상어가 3칸을 이동하는데, 4가지 이동방향이 가능(상, 하, 좌, 우)
   격자 범위를 벗어나는 곳으로는 이동이 불가능하고, 가능한 방법 중에 제외되는 물고기가 가장 많은 방법으로
   이동하면 된다.
   이 때 제외되는 물고기가 가장 많은 방법이 여러가지라면 사전 순으로 빠른 것을 하게 되는데
   사전 순은 상: 1, 좌: 2, 하: 3, 우: 4라고 주어졌을 때 숫자가 작은 것을 먼저한다.
   ex.) 상상상(111) < 상좌하(123) 이므로 111을 하면 된다.
4. 연습 2번 전의 물고기 냄새를 제거한다.
5. (1)에서 시전한 복제가 완료되고 물고기들이 복제된다.

 

문제 풀이

우선 물고기를 저장할 때 이차원 벡터를 이용해서 물고기들을 저장할 것이다.

후에 복제 시전은 아래와 같은 로직으로 구현하려고 생각했다.

1. 물고기를 복제할 복제 벡터에 정보들을 담아둔다.
2. 물고기를 이동시키는데,
   범위 벗어나는지, 상어가 있는 칸인지, 물고기 냄새가 남아있는지 체크한다.
   물고기 냄새를 체크할 때에는 현재 연습보다 2번 이내로 남아있는 냄새인지만 check하면
   (4)의 조건은 무시해도 된다.
3. 상어가 이동하는데, 모든 경우의 수 64가지를 check해주면 된다.
4. 물고기 냄새를 제거하는 로직은 필요없다.
5. 복제 벡터에 담아둔 물고기들을 복제한다.

/*
* 백준 23290번 마법사 상어와 복제
* https://www.acmicpc.net/problem/23290
* 구현 / 시뮬레이션
*/
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Fish {
public:
	int r;
	int c;
	int dir;
	bool isDead;
	Fish(int r, int c, int dir, bool isDead) {
		this->r = r;
		this->c = c;
		this->dir = dir;
		this->isDead = isDead;
	}
};

pair<int, int> fishDir[9] = {
	{-1, -1},
	{0, -1},
	{-1, -1},
	{-1, 0},
	{-1, 1},
	{0, 1},
	{1, 1},
	{1, 0},
	{1, -1}
};

pair<int, int> sharkDir[5] = {
	{-1, -1},
	{-1, 0},
	{0, -1},
	{1, 0},
	{0, 1}
};

vector<vector<vector<Fish>>> fishVec(5, vector<vector<Fish>>(5, vector<Fish>()));
vector<Fish> copyVec;
vector<Fish> moveVec;
pair<int, int> curSharkPoint;
int maxRemovedsharkMove;
int maxRemovedFishCnt;
int smellMap[5][5];
int fishCntTmpMap[5][5];
int fishCnt;
int spellCnt;
int ans;

void findSharkMove(int idx, int prevMove, int removedFishCnt, int prevR, int prevC) {
	if (idx == 4) {
		if (maxRemovedFishCnt < removedFishCnt) {
			maxRemovedFishCnt = removedFishCnt;
			maxRemovedsharkMove = prevMove;
		}
		else if (maxRemovedFishCnt == removedFishCnt) {
			maxRemovedsharkMove = min(maxRemovedsharkMove, prevMove);
		}
		return;
	}
	else {
		prevMove *= 10;
		for (int i = 1; i <= 4; i++) {
			int nxtR = prevR + sharkDir[i].first;
			int nxtC = prevC + sharkDir[i].second;
			if (nxtR > 4 || nxtR < 1 || nxtC > 4 || nxtC < 1) { continue; }
			int originalFishCnt = fishCntTmpMap[nxtR][nxtC];
			fishCntTmpMap[nxtR][nxtC] = 0;
			findSharkMove(idx + 1, prevMove + i, removedFishCnt + originalFishCnt, nxtR, nxtC);
			fishCntTmpMap[nxtR][nxtC] = originalFishCnt;
		}
	}
}

void go(int idx) {

	if (idx > spellCnt) { return; }

	// 1. 물고기 복제 - 5에서 최종복제됨
	copyVec.clear();
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < fishVec[i][j].size(); k++) {
				if (!fishVec[i][j][k].isDead) {
					copyVec.push_back(fishVec[i][j][k]);
				}
			}
		}
	}

	// 2. 물고기 한 칸 이동
	/*
	* - 1. 상어 있는 칸 이동 불가
	* - 2. 물고기 냄새 있는 칸 이동 불가 (해당 칸 물고기 냄새 idx보다 2 이하면 이동 불가)
	* - 3. 범위 벗어나는 칸 이동 불가
	* 이동 가능할 때 까지 45도 반시계 회전(이동방향에서 -1, 0이면 8 9면 1)
	*/
	moveVec.clear();
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < fishVec[i][j].size(); k++) {
				if (!fishVec[i][j][k].isDead) {

					int curDir = fishVec[i][j][k].dir;

					int turnIdx = 8;

					while (turnIdx--) {
						int nxtR = i + fishDir[curDir].first;
						int nxtC = j + fishDir[curDir].second;
						if ((nxtR > 4 || nxtC > 4 || nxtR < 1 || nxtC < 1) ||
							(nxtR == curSharkPoint.first && nxtC == curSharkPoint.second) ||
							(smellMap[nxtR][nxtC] != 0 && idx - smellMap[nxtR][nxtC] <= 2)) {
							curDir -= 1;
							if (curDir == 0) { curDir = 8; }
							continue;
						}
						else {
							moveVec.push_back(Fish(nxtR, nxtC, curDir, false));
							fishVec[i][j][k].isDead = true;
							break;
						}
					}
				}

			}
		}
	}
	for (Fish fish : moveVec) {
		fishVec[fish.r][fish.c].push_back(fish);
	}

	// 3. 상어 3칸 이동 상, 하, 좌, 우 
	/*
	* 물고기 방향 알아내면 제외 시키고 냄새 남기기.
	*/
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			fishCntTmpMap[i][j] = 0;
			for (int k = 0; k < fishVec[i][j].size(); k++) {
				if (!fishVec[i][j][k].isDead) { fishCntTmpMap[i][j]++; }
			}
		}
	}
	maxRemovedFishCnt = -1;
	findSharkMove(1, 0, 0, curSharkPoint.first, curSharkPoint.second);

	int firstMove = maxRemovedsharkMove / 100;
	int secondMove = (maxRemovedsharkMove - (firstMove * 100)) / 10;
	int thirdMove = maxRemovedsharkMove - (firstMove * 100) - (secondMove * 10);

	//cout << firstMove << " " << secondMove << " " << thirdMove << "\n";

	//first
	curSharkPoint.first += sharkDir[firstMove].first;
	curSharkPoint.second += sharkDir[firstMove].second;
	int liveFishCnt = 0;
	for (int i = 0; i < fishVec[curSharkPoint.first][curSharkPoint.second].size(); i++) {
		if (!fishVec[curSharkPoint.first][curSharkPoint.second][i].isDead) {
			liveFishCnt++;
		}
	}
	if (liveFishCnt > 0) {
		smellMap[curSharkPoint.first][curSharkPoint.second] = idx;
		fishVec[curSharkPoint.first][curSharkPoint.second].clear();
	}
	
	//second
	curSharkPoint.first += sharkDir[secondMove].first;
	curSharkPoint.second += sharkDir[secondMove].second;
	liveFishCnt = 0;
	for (int i = 0; i < fishVec[curSharkPoint.first][curSharkPoint.second].size(); i++) {
		if (!fishVec[curSharkPoint.first][curSharkPoint.second][i].isDead) {
			liveFishCnt++;
		}
	}
	if (liveFishCnt > 0) {
		smellMap[curSharkPoint.first][curSharkPoint.second] = idx;
		fishVec[curSharkPoint.first][curSharkPoint.second].clear();
	}

	//third
	curSharkPoint.first += sharkDir[thirdMove].first;
	curSharkPoint.second += sharkDir[thirdMove].second;
	liveFishCnt = 0;
	for (int i = 0; i < fishVec[curSharkPoint.first][curSharkPoint.second].size(); i++) {
		if (!fishVec[curSharkPoint.first][curSharkPoint.second][i].isDead) {
			liveFishCnt++;
		}
	}
	if (liveFishCnt > 0) {
		smellMap[curSharkPoint.first][curSharkPoint.second] = idx;
		fishVec[curSharkPoint.first][curSharkPoint.second].clear();
	}
	
	// 4. 냄새 제거. - 어차피 2 이하인지 검사하므로 할 필요 X

	// 5. 물고기 복제
	for (Fish fish : copyVec) {
		fishVec[fish.r][fish.c].push_back(fish);
	}

	go(idx + 1);
}

int main() {
	cin >> fishCnt >> spellCnt;

	int r, c, dir;
	for (int i = 1; i <= fishCnt; i++) {
		cin >> r >> c >> dir;
		fishVec[r][c].push_back(Fish(r, c, dir, false));
	}

	cin >> curSharkPoint.first >> curSharkPoint.second;

	go(1);

	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 0; k < fishVec[i][j].size(); k++) {
				if (!fishVec[i][j][k].isDead) {
					ans++;
				}
			}
		}
	}

	cout << ans;

	return 0;
}

 

틀린 이유

처음에 물고기를 이동시킬 때, vector의 erase(iterator) 메서드를 이용했는데,

알고보니 이 메서드의 시간 복잡도가 O(N)이였다.

벡터의 경우 erase시키면 한 칸씩 좌측으로 밀어주기 때문에 몇십만 개의 데이터가 계속 삭제되면

시간 초과가 날 수 밖에 없다.

 

따라서 이동시킨 후에는 지우지 않고 그냥 해당 물고기가 존재하지 않는 물고기라는 처리만 해주면 된다.