[C++] 백준 19237번 어른 상어

19237번: 어른 상어

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

구현 / 시뮬레이션 문제.

테스트 케이스들이 잘 나와 있어서 테스트 케이스만 맞춰도 맞출 수 있다.

 

문제 조건

문제의 조건들은 다음과 같다.

상어의 정보

• 상어는 1 ~ M 번호를 가지고 있고, 중복되지 않는다.
• 상어들은 서로 내쫓으려고 하는데,
  숫자가 낮을 수록 강한 상어이다.

격자 정보

• N x N 크기의 격자에, M마리의 상어가 한마리씩 존재.
• 각 칸에 상어의 냄새가 존재할 수 있음.

상어 이동 관련

• 상어의 이동 관련은 다음과 같은 순서로 이루어진다.
  1. 상어가 자신의 냄새를 해당 칸에 뿌린다.
  2. 1초마다 상, 하, 좌, 우 중 한 칸을 이동한다.
  3. 이 때, 냄새는 K초 이후에 제거된다.
• 상어의 이동은 다음과 같은 우선순위를 갖는다.
  1. 냄새가 없는 칸
  2. 자신의 냄새가 있는 칸
     • 여기서 주의할 점은, 상, 하, 좌, 우에 대해 1번을 먼저 고려한 후 2번을 그 다음 고려해줘야 한다는 점이다.
  3. 가능한 칸이 여러개라면 상어의 현재 보는 방향에 따른 우선순위에 따라 이동하게 된다.
• 상어가 모두 이동한 후에, 상어가 여러마리 있는 칸에는 가장 작은 번호의 상어만 살아남는다.

 

위 같은 조건들이 있을 때, 1번 상어만 살아남을 때까지 몇 초가 걸리는 지 계산하고,

1,000초를 넘으면 -1을 출력하면 된다.

 

문제 구현

문제의 정보들을 다음과 같은 구조체를 만들어서 저장했다.

• 상어 구조체
  1. 좌표(r, c)
  2. 현재 상어가 보는 방향
  3. 상어가 보는 방향에 따라 우선순위를 고려해야 하는 방향
  4. 현재 상어가 살아있는 지?
• 격자 관련 구조체
  1. 현재 칸의 상어의 수
  2. 현재 칸의 냄새의 번호
  3. 현재 칸의 냄새를 남았을 때의 idx
• 이동 관련 로직
  1. 모든 상어들에 대해 냄새를 남김.
  2. 살아있는 상어들 이동
     • 보는 방향에 따라 다르게 우선순위 정함.
       1. 다음 칸의 냄새가 없거나
       2. 자기 자신의 냄새가 있는 지 확인
  3. 두 마리 이상 상어 이는 칸에서 제일 작은 번호의 상어만 남긴다.

 

위처럼 만들어서 구현하면 풀 수 있었다.

문제 코드

 

/*
* 백준 19237번 어른 상어
* https://www.acmicpc.net/problem/19237
* - 구현 / 시뮬레이션
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Shark {
	int number = -1;
	int r = 0;
	int c = 0;
	int watchingDirection = 0;
	int priorityDirection[5][5];
	bool isRemoved = false;
};

struct SharkMapInfo {
	int sharkCnt = 0;
	int smellNumber = -1;
	int smellIdx = -1;
};

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

int widthHeight, sharkCnt, smellRemainTime;
SharkMapInfo sharkMapInfo[21][21];
vector<Shark> sharkVec;
int result = -1;

bool comp(Shark s1, Shark s2) {
	return s1.number < s2.number;
}

void go(int idx) {
	if (idx > 1000) return;

	//0. 냄새 제거
	for (int r = 1; r <= widthHeight; r++) {
		for (int c = 1; c <= widthHeight; c++) {
			if (sharkMapInfo[r][c].smellIdx > 0) {
				sharkMapInfo[r][c].smellIdx--;
				
				if (sharkMapInfo[r][c].smellIdx == 0) {
					sharkMapInfo[r][c].smellIdx = -1;
					sharkMapInfo[r][c].smellNumber = -1;
				}
			}
		}
	}

	//1. 냄새 남기기
	for (int i = 0; i < sharkCnt; i++) {
		if (!sharkVec[i].isRemoved) {
			sharkMapInfo[sharkVec[i].r][sharkVec[i].c].smellNumber = sharkVec[i].number;
			sharkMapInfo[sharkVec[i].r][sharkVec[i].c].smellIdx = smellRemainTime;
		}
	}

	//2. 이동
	for (int i = 0; i < sharkCnt; i++) {
		if (!sharkVec[i].isRemoved) {
			bool sharkMoved = false;
			// - 1. 냄새가 없는 지 Check
			for (int j = 1; j <= 4; j++) {
				int dir = sharkVec[i].priorityDirection[sharkVec[i].watchingDirection][j];
				int nxtR = sharkVec[i].r + directions[dir].first;
				int nxtC = sharkVec[i].c + directions[dir].second;

				if (nxtR < 1 || nxtR > widthHeight || nxtC < 1 || nxtC > widthHeight || sharkMapInfo[nxtR][nxtC].smellNumber != -1) continue;
				
				sharkMapInfo[sharkVec[i].r][sharkVec[i].c].sharkCnt--;
				sharkVec[i].r = nxtR;
				sharkVec[i].c = nxtC;
				sharkVec[i].watchingDirection = dir;
				sharkMapInfo[nxtR][nxtC].sharkCnt++;
				sharkMoved = true;
				break;
			}

			// - 2. 같은 냄새 있는 지 Check
			if (!sharkMoved) {
				for (int j = 1; j <= 4; j++) {
					int dir = sharkVec[i].priorityDirection[sharkVec[i].watchingDirection][j];
					int nxtR = sharkVec[i].r + directions[dir].first;
					int nxtC = sharkVec[i].c + directions[dir].second;

					if (nxtR < 1 || nxtR > widthHeight || nxtC < 1 || nxtC > widthHeight || sharkMapInfo[nxtR][nxtC].smellNumber != sharkVec[i].number) continue;

					sharkMapInfo[sharkVec[i].r][sharkVec[i].c].sharkCnt--;
					sharkVec[i].r = nxtR;
					sharkVec[i].c = nxtC;
					sharkVec[i].watchingDirection = dir;
					sharkMapInfo[nxtR][nxtC].sharkCnt++;
					break;
				}
			}

		}
	}

	//3. 두 마리 이상 상어 있는 칸에서 제일 작은 번호만 남기기
	for (int r = 1; r <= widthHeight; r++) {
		for (int c = 1; c <= widthHeight; c++) {
			if (sharkMapInfo[r][c].sharkCnt > 1) {
				bool minimumFind = false;
				for (int k = 0; k < sharkCnt; k++) {
					if (!sharkVec[k].isRemoved && sharkVec[k].r == r && sharkVec[k].c == c) {
						if (!minimumFind) minimumFind = true;
						else {
							sharkVec[k].isRemoved = true;
							sharkMapInfo[r][c].sharkCnt--;
						}
					}
				}
			}
		}
	}

	int aliveSharkCnt = 0;
	for (int i = 0; i < sharkCnt; i++) {
		if (!sharkVec[i].isRemoved) aliveSharkCnt++;
	}

	if (aliveSharkCnt == 1) {
		result = idx;
		return;
	}
	else go(idx + 1);
}

int main() {
	cin >> widthHeight >> sharkCnt >> smellRemainTime;

	int input;
	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			cin >> input;
			if (input != 0) {
				sharkMapInfo[i][j].sharkCnt++;
				sharkVec.push_back({ input, i, j });
			}
		}
	}

	sort(sharkVec.begin(), sharkVec.end(), comp);

	int watchDir;
	for (int i = 0; i < sharkCnt; i++) {
		cin >> watchDir;
		sharkVec[i].watchingDirection = watchDir;
	}

	for (int i = 0; i < sharkCnt; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 1; k <= 4; k++) {
				cin >> sharkVec[i].priorityDirection[j][k];
			}
		}
	}

	go(1);

	cout << result;

	return 0;

}

처음에 로직을 다 잘 짰다고 생각했는데 재귀에서 터져서 뭐지 싶었는데,

제출해보니 맞을 수 있었다.

Visual Studio의 Stack Memory를 더 할당하니 해결할 수 있었다.