[BOJ][삼성기출] 19237. 어른 상어

문제 접근

1. 시뮬레이션 문제이다.
2. 모든 상어가 자신의 위치에 냄새를 뿌리고 시작한다.
3. 1초마다 상어는 동시에 상하좌우로 인접한 칸 중 하나로 이동한 뒤 냄새를 뿌린다.
   냄새는 1초에 1씩 사라지며 k시간 동안 유지된다.

   이동 우선순위 정보를 저장하기 위해 각 상어의 구조체 내에 우선순위 정보를 저장하기 위한 배열을 두고 문제를 풀었다.

4. 관건은 격자 위에 여러 마리의 상어가 존재할 때다.

   여러 마리의 상어가 한 격자 위에 존재할 수 있는 경우는 빈 격자에 동시에 여러 마리의 상어가 위치할 때다.
   이때 기존의 map을 실시간으로 업데이트 하게 되면, 동시에 이동 이라는 조건을 충족시키지 못하므로 n_map 을 두어 n_map에 업데이트된 상어의 정보를 저장하였다.
   즉, map을 기반으로 상어의 이동 여부를 결정하며, 이동 후 정보는 n_map에 저장했다.
   가장 작은 번호를 가진 상어만 생존하므로, n_map을 업데이트 할 때 이미 상어에 대한 정보가 있는지 확인한 후, 현재 이동시키고자 하는 상어의 번호가 더 적을 경우에만 업데이트 해주었다.
   격자 밖으로 쫓겨나는 상어에 대해서는 상어의 live를 false로 업데이트 해주었다.

5. 아기 상어, 청소년 상어 문제와 마찬가지로 두 개의 자료구조의 sync를 맞추는 게 중요한 문제다.

풀이

#include <iostream>
#include <cstdio>
using namespace std;

typedef struct intfo {
	int s_num;
	int k;
} info;
info map[21][21];

typedef struct shark {
	int x;
	int y;
	int dir;
	int pri[5][5];
	bool live;
};
shark Shark[401];
int N, M, k, rst;

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

void input() {
	cin >> N >> M >> k;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int s_num;
			cin >> s_num;
			if (s_num > 0) {
				map[i][j].s_num = s_num;
				Shark[s_num].x = i;
				Shark[s_num].y = j;
				Shark[s_num].live = true;
			}
			else {
				map[i][j].s_num = -1;
			}
			map[i][j].k = 0;
		}
	}
	for (int s_num = 1; s_num <= M; s_num++){
		cin >> Shark[s_num].dir;
	}
	for (int s_num = 1; s_num <= M; s_num++) {
		for (int i = 1; i <= 4; i++) {
			for (int j = 1; j <= 4; j++) {
				cin >> Shark[s_num].pri[i][j];
			}
		}
	}
	rst = 0;
}

int is_left_one() {
	for (int i = 2; i <= M; i++) {
		if (Shark[i].live) return false;
	}
	return true;
}

int is_range(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < N) return true;
	return false;
}

void move_shark() {
	info n_map[21][21];
	for (int i = 0; i < N; i++) { //copy map
		for (int j = 0; j < N; j++) {
			n_map[i][j] = map[i][j];
		}
	}
	for (int s_num = 1; s_num <= M; s_num++) {
		if (!Shark[s_num].live) continue;
		int x = Shark[s_num].x;
		int y = Shark[s_num].y;
		int dir = Shark[s_num].dir;
		bool move_done = false;

		for (int i = 1; i <= 4; i++) { // no smell
			int ndir = Shark[s_num].pri[dir][i];
			int nx = x + dx[ndir];
			int ny = y + dy[ndir];
			if (!is_range(nx, ny)) continue;
			if (map[nx][ny].s_num == -1) { // can go
				move_done = true;
				if (n_map[nx][ny].s_num != -1) { // shark already exists
					if (s_num < n_map[nx][ny].s_num) { // my number is smaller than old one
						Shark[n_map[nx][ny].s_num].live = false; // kill the old shrak
					}
					else { // my number is bigger than old one
						Shark[s_num].live = false;
						break;
					}
				}
				n_map[nx][ny].s_num = s_num;
				n_map[nx][ny].k = k;
				Shark[s_num].dir = ndir;
				Shark[s_num].x = nx;
				Shark[s_num].y = ny;
				break;
			}
		}
		if (move_done) continue;
		for (int i = 1; i <= 4; i++) { // own smell
			int ndir = Shark[s_num].pri[dir][i];
			int nx = x + dx[ndir];
			int ny = y + dy[ndir];
			if (!is_range(nx, ny)) continue;
			if (map[nx][ny].s_num == s_num) {
				n_map[nx][ny].s_num = s_num;
				n_map[nx][ny].k = k;
				Shark[s_num].dir = ndir;
				Shark[s_num].x = nx;
				Shark[s_num].y = ny;
				break;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] = n_map[i][j];
		}
	}

}

void decrease_k() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j].k > 0) map[i][j].k--;
			if (map[i][j].k == 0) map[i][j].s_num = -1;
		}
	}
	for (int s_num = 1; s_num <= M; s_num++) {
		if (!Shark[s_num].live) continue;
		int x = Shark[s_num].x;
		int y = Shark[s_num].y;
		map[x][y].k = k;
	}
}

void solve() {
	for (int i = 1; i <= M; i++) {
		int x = Shark[i].x;
		int y = Shark[i].y;
		map[x][y].k = k;
	}
	while (!is_left_one()) {
		if (rst == 1000) {
			rst = -1;
			break;
		}
		rst++;
		move_shark();
		decrease_k();
	}
}

int main() {
	input();
	solve();
	cout << rst << endl;
}

1. 불필요한 연산을 하는 코드라고 생각한다.
   n_map에 k를 업데이트 한 뒤 전체적으로 k를 감소시키고 있다.
   이럴 경우 상어가 막 도착해서 k값이 4인 경우까지 k값이 감소가 되어서 상어의 현재 위치를 기반으로 k값을 새로 세팅해 주고 있다.
   다 푼 뒤 생각한 풀이 방법

   1) 상어를 이동시킨다. 이동 위치를 저장하는 구조체를 따로 만들어 정보를 저장해 둔다.
   2) 전체적으로 k를 감소시킨다.
   3) 가장 적은 번호의 상어부터 map에 update를 시킨다. 이때 k가 세팅된다.
   4) update하고자 하는 위치에 상어가 없다면, 상어 정보를 해당 위치에 update 한다.
   5) update하고자 하는 위치에 상어가 이미 있고(상어 번호가 이미 세팅된 상태), 나의 번호와 같을 경우 상어는 자신이 냄새를 뿌린 곳으로 간 것이다.
   6) update하고자 하는 위치에 상어가 이미 있고, 나의 번호와 다를 경우 그 상어는 격자 밖으로 쫓겨난다. (가장 작은 번호의 상어부터 update를 하는데 이미 자신보다 더 작은 번호의 상어가 도달했다는 뜻이므로)

2. 화이팅!