백준 - 어른 상어 (19237)

1. 문제

문제 링크

2. 풀이

상어 시리즈의 마지막 문제입니다.
특정 알고리즘은 요구하지 않고 상어의 움직임만 구현하면 됩니다.

1. 필요한 자료구조 선언

int my[4] = { -1, 1, 0, 0 };
int mx[4] = { 0, 0, -1, 1 };
int sharkInfo[MAX][4];
int priorityDirs[MAX][4][4];
int sea[SIZE][SIZE];
int smellCount[SIZE][SIZE];
queue<pair<int, int>> smellOfSea[MAX];
queue<int> sharks;

• sharkInfo: 상어의 현재 정보를 저장하는 2차원 배열
  • sharkInfo[1][0]: 1번 상어의 y좌표
  • sharkInfo[1][1]: 1번 상어의 x좌표
  • sharkInfo[1][2]: 1번 상어가 현재 바라보는 방향
  • sharkInfo[1][3]: 1번 상어가 바다에서 나갔는지 여부
• priorityDirs: 상어가 우선으로 하는 방향의 순서를 저장하는 3차원 배열
  • priorityDirs[1][0][0]: 1번 상어가 북쪽을 바라볼 때 첫 번째로 바라보는 방향
  • priorityDirs[1][0][1]: 1번 상어가 북쪽을 바라볼 때 두 번째로 바라보는 방향
  • 이하 생략...
• sea: 현재 바다 상황을 나타내는 2차원 배열
• smellCount: 현재 좌표에 상어의 냄새가 얼마나 뿌려졌는지 세는 2차원 배열
• smellOfSea: 상어가 뿌린 냄새의 좌표를 저장하는 큐 배열
  • smellOfSea[2]: 2번 상어가 냄새를 뿌린 좌표 리스트가 순서대로 담겨 있다.
• sharks: 현재 남아있는 상어 번호들을 내림차순으로 저장하는 큐

저는 항상 문제를 보고 '어떻게 풀어야겠다' 계획을 세우고 구현에 들어가는데요,
이 때 가장 중요한 부분이 자료구조 선언입니다.
어떤 자료구조를 선택하느냐에 따라 문제 난이도가 달라집니다.

2. 냄새 뿌리기

size = sharks.size();

// 냄새 뿌리기
while (size--) {
	int sharkNum = sharks.front();
	int y = sharkInfo[sharkNum][0];
	int x = sharkInfo[sharkNum][1];

	sharks.push(sharkNum);
	sharks.pop();

	sea[y][x] = sharkNum;
	smellCount[y][x]++; // 냄새 카운트 증가
	smellOfSea[sharkNum].push({ y, x }); // 냄새 좌표 추가
}

sharks에 저장된 상어 번호들을 순회하며
현재 상어가 위치한 자리에 냄새를 뿌리면 됩니다.

3. 상어 이동시키기

// 상어 이동
while (size--) {
	int sharkNum = sharks.front();
	int y = sharkInfo[sharkNum][0];
	int x = sharkInfo[sharkNum][1];
	int curDir = sharkInfo[sharkNum][2];

	sharks.push(sharkNum);
	sharks.pop();

	int emptyNth = -1, mySmellNth = -1;

	for (int i = 0; i < 4; i++) {
		int ny = y + my[priorityDirs[sharkNum][curDir][i]];
		int nx = x + mx[priorityDirs[sharkNum][curDir][i]];

		if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;

		// 빈 칸
		if (sea[ny][nx] == 0) {
			emptyNth = i;
			break; // 빈 칸일 땐 바로 빠져 나옴
		}
		// 내 냄새
		else if (sea[ny][nx] == sharkNum && mySmellNth == -1) {
			mySmellNth = i;
		}
	}

	// 빈 칸 우선
	int priorityNth = emptyNth != -1 ? emptyNth : mySmellNth;

	// 상어 좌표, 방향 갱신
	sharkInfo[sharkNum][0] = y + my[priorityDirs[sharkNum][curDir][priorityNth]];
	sharkInfo[sharkNum][1] = x + mx[priorityDirs[sharkNum][curDir][priorityNth]];
	sharkInfo[sharkNum][2] = priorityDirs[sharkNum][curDir][priorityNth];
}

sharks에 저장된 상어 번호들을 순회하며
상어들이 각각 우선시하는 방향을 순회하며 갈 수 있으면 그 좌표로 이동시킵니다.
여기서 주의할 점은 빈 칸을 우선해서 움직여야 합니다.
예를 들어 첫 번째로 바라본 방향이 본인의 냄새여도 세 번째로 바라본 방향이 빈 칸이라면
세 번째로 바라본 방향으로 이동해야합니다.

3. 상어 경합하기

while (size--) {
	int sharkNum = sharks.front();
	int y = sharkInfo[sharkNum][0];
	int x = sharkInfo[sharkNum][1];

	sharks.push(sharkNum);
	sharks.pop();

	// 내 냄새가 아닐 때
	if (sea[y][x] != sharkNum) {
		sharkInfo[sea[y][x]][3] = 1; // 이미 있던 상어 내보내기
		sea[y][x] = sharkNum; // 현재 상어 번호로 덮어씌우기
	}
}

sharks에 저장된 상어 번호들을 순회하며
내 냄새가 아닐 때 이미 있던 상어를 내보내고 (sharkInfo[sea[y][x]][3] = 1)
현재 상어 번호로 덮어씌웁니다.
이렇게 하면 자연스럽게 번호가 큰 상어들이 내보내지게끔 구현할 수 있습니다.

문제의 예시를 보면 두 번째 턴에서 좌표 (2, 4)에 2번 상어과 4번 상어가 겹치게 됩니다.
sharks의 저장된 상어 번호들은 내림차순으로 저장되어 있기 때문에
4번 상어가 먼저 (2, 4)를 영역 표시한 후에 2번 상어가 (2, 4)를 영역 표시하려 할 때
이미 4번으로 영역 표시가 되어있기 때문에 4번을 내보내고 2번으로 덮어씌우게 됩니다.

4. 남아있는 상어만 골라내기

// 남아있는 상어만 골라내기
while (size--) {
	int sharkNum = sharks.front();

	sharks.pop();

	// 나간 애는 넘어감
	if (sharkInfo[sharkNum][3]) continue;

	sharks.push(sharkNum);
}

3번 과정에서 4번이 나갔기 때문에 sharks에는 차례대로 3, 2, 1의 상어가 들어갑니다.

5. 냄새 제거하기

// 냄새 제거
for (int i = 1; i <= m; i++) {
	if (smellOfSea[i].empty()) continue;

	int y = smellOfSea[i].front().first;
	int x = smellOfSea[i].front().second;

	smellOfSea[i].pop();

	if (--smellCount[y][x] == 0) {
		sea[y][x] = 0;
	}
}

냄새 제거는 간단합니다.
각 상어마다 냄새를 뿌린 좌표를 큐에 저장했으니
큐에서 하나씩 좌표를 빼와서 그 부분을 지워주면 됩니다.

3. 전체 코드

#define SIZE 20
#define MAX SIZE * SIZE + 1
#define LIMIT 1000
#include <bits/stdc++.h>

using namespace std;

int n, m, k;
int my[4] = { -1, 1, 0, 0 };
int mx[4] = { 0, 0, -1, 1 };
int sharkInfo[MAX][4];
int priorityDirs[MAX][4][4];
int sea[SIZE][SIZE];
int smellCount[SIZE][SIZE];
queue<pair<int, int>> smellOfSea[MAX];
queue<int> sharks;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> sea[i][j];

			if (sea[i][j] > 0) {
				// 상어 좌표 저장
				sharkInfo[sea[i][j]][0] = i;
				sharkInfo[sea[i][j]][1] = j;
			}
		}
	}

	for (int i = 1; i <= m; i++) {
		cin >> sharkInfo[i][2];
		sharkInfo[i][2]--;
		sharks.push(m - i + 1);
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> priorityDirs[i][j][k];
				priorityDirs[i][j][k]--;
			}
		}
	}

	int ans = -1, time = 0, size;

	while (time < LIMIT) {
		size = sharks.size();

		// 냄새 뿌리기
		while (size--) {
			int sharkNum = sharks.front();
			int y = sharkInfo[sharkNum][0];
			int x = sharkInfo[sharkNum][1];

			sharks.push(sharkNum);
			sharks.pop();

			sea[y][x] = sharkNum;
			smellCount[y][x]++; // 냄새 카운트 증가
			smellOfSea[sharkNum].push({ y, x }); // 냄새 좌표 추가
		}

		size = sharks.size();

		// 상어 이동
		while (size--) {
			int sharkNum = sharks.front();
			int y = sharkInfo[sharkNum][0];
			int x = sharkInfo[sharkNum][1];
			int curDir = sharkInfo[sharkNum][2];

			sharks.push(sharkNum);
			sharks.pop();

			int emptyNth = -1, mySmellNth = -1;

			for (int i = 0; i < 4; i++) {
				int ny = y + my[priorityDirs[sharkNum][curDir][i]];
				int nx = x + mx[priorityDirs[sharkNum][curDir][i]];

				if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;

				// 빈 칸
				if (sea[ny][nx] == 0) {
					emptyNth = i;
					break; // 빈 칸일 땐 바로 빠져 나옴
				}
				// 내 냄새
				else if (sea[ny][nx] == sharkNum && mySmellNth == -1) {
					mySmellNth = i;
				}
			}

			// 빈 칸 우선
			int priorityNth = emptyNth != -1 ? emptyNth : mySmellNth;

			// 상어 좌표, 방향 갱신
			sharkInfo[sharkNum][0] = y + my[priorityDirs[sharkNum][curDir][priorityNth]];
			sharkInfo[sharkNum][1] = x + mx[priorityDirs[sharkNum][curDir][priorityNth]];
			sharkInfo[sharkNum][2] = priorityDirs[sharkNum][curDir][priorityNth];
		}

		size = sharks.size();

		// 상어 경합
		while (size--) {
			int sharkNum = sharks.front();
			int y = sharkInfo[sharkNum][0];
			int x = sharkInfo[sharkNum][1];

			sharks.push(sharkNum);
			sharks.pop();

			// 내 냄새가 아닐 때
			if (sea[y][x] != sharkNum) {
				sharkInfo[sea[y][x]][3] = 1; // 이미 있던 상어 내보내기
				sea[y][x] = sharkNum; // 현재 상어 번호로 덮어씌우기
			}
		}

		size = sharks.size();

		// 남아있는 상어만 골라내기
		while (size--) {
			int sharkNum = sharks.front();

			sharks.pop();

			// 나간 애는 넘어감
			if (sharkInfo[sharkNum][3]) continue;

			sharks.push(sharkNum);
		}

		time++;

		// 1번만 남았을 때
		if (sharks.size() == 1) {
			ans = time;
			break;
		}

		if (time < k) continue;

		// 냄새 제거
		for (int i = 1; i <= m; i++) {
			if (smellOfSea[i].empty()) continue;

			int y = smellOfSea[i].front().first;
			int x = smellOfSea[i].front().second;

			smellOfSea[i].pop();

			if (--smellCount[y][x] == 0) {
				sea[y][x] = 0;
			}
		}
	}

	cout << ans;

	return 0;
}