[백준] 19237번 어른 상어

19237번: 어른 상어

격자 벡터엔 칸마다 냄새를 남긴 상어의 번호, 남은 시간을 저장하고

상어 벡터엔 상어 번호, x 좌표, y 좌표, 방향을 저장한다.

상어 방향 3차원 배열은 [상어 번호][방향][순위]를 인덱스로 가지고 값은 그때의 방향이다.

 

1. 상어 벡터를 처음부터 끝까지 돌면서

상어 방향 배열을 이용해

현재 상어의 방향일 때의 우선순위에 맞게

이동할 수 있는 빈칸을 찾는다.

 

→이동할 수 있는 빈칸이 있다면

임시 벡터에 상어 번호, 그 칸의 위치, 그때의 방향을 저장한다.

 

→이동할 수 있는 빈칸이 없다면

자신의 냄새가 있는 칸을 찾은 뒤

임시 벡터에 상어 번호, 그 칸의 위치, 그때의 방향을 저장한다.

 

2. 상어 벡터 끝까지 다 돌았으면

격자 벡터를 돌면서 각 칸에 있는 냄새의 남은 시간을 - 1 해준다.

남은 시간이 0이 되면 저장된 상어 번호도 0으로 만들어주어 빈칸으로 만들어버린다.

 

3. 이제 새 냄새를 뿌려야 할 차례이므로

임시 벡터를 처음부터 끝까지 돌면서

격자 벡터에 상어 번호와 남은 시간 K를 저장한다.

 

이때, 냄새를 뿌릴 칸이 겹치는 상어들이 있으면

번호가 더 작은 상어가 차지하게 된다.

임시 벡터에서의 상어 번호는 오름차순으로 정렬된 상태이므로

앞의 상어가 새 냄새를 뿌리면

뒤의 상어들은 그 칸에 냄새를 뿌리지 못하고 사라진다.

 

chk 배열을 만들어 현재 상어가 냄새를 뿌릴 칸이

체크되지 않은 칸이면 냄새를 뿌린 뒤 (상어 번호, 시간 저장) 체크해두고

체크된 칸이면 상어 번호를 0으로 만들어준다. (나가리)

 

임시 벡터를 끝까지 돌았으면

상어 번호가 0이 아닌 애들만 상어 벡터에 저장시킨다.

 

4. 이 과정을 반복하다가

상어 벡터의 크기가 1이고 그 상어 번호가 1일 때 반복 횟수를 출력하고

1000회 넘게 반복될 경우 -1을 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, K, x, y, d, n, res;
int shark[402][5][4], dx[5] = { 0, -1, 1, 0, 0 }, dy[5] = { 0, 0, 0, -1, 1 };
class SharkInfo {
public:
	int num, x, y, d, sec;
	SharkInfo(int num, int x, int y, int d) { // 상어 번호, x 좌표, y 좌표, 방향
		this->num = num, this->x = x, this->y = y, this->d = d;
	}
	SharkInfo(int num, int sec) { // 상어 번호, 남은 시간
		this->num = num, this->sec = sec;
	}
	bool operator<(SharkInfo &SharkInfo) {
		return this->num < SharkInfo.num;
	}
};

vector <SharkInfo> v, arr[21];

void Move() {
	vector <SharkInfo> tmp;
	for (int i = 0; i < v.size(); i++) {
		bool out = false;
		for (int j = 0; j < 4; j++) { // 처음엔 빈 칸이 있으면 빈 칸으로
			d = shark[v[i].num][v[i].d][j], x = v[i].x + dx[d], y = v[i].y + dy[d];
			if (x >= 0 && x < N && y >= 0 && y < N && arr[x][y].num == 0) {
				tmp.push_back(SharkInfo(v[i].num, x, y, d));
				out = true;
				break;
			}
		}
		if (out) continue;
		for (int j = 0; j < 4; j++) { // 빈 칸이 없으면 자기 냄새가 있는 곳으로
			d = shark[v[i].num][v[i].d][j], x = v[i].x + dx[d], y = v[i].y + dy[d];
			if (x >= 0 && x < N && y >= 0 && y < N && arr[x][y].num == v[i].num) {
				tmp.push_back(SharkInfo(v[i].num, x, y, d));
				break;
			}
		}
	}
	for (int i = 0; i < N; i++) { // 냄새 남은 시간 1초씩 줄어듦
		for (int j = 0; j < N; j++) {
			if (arr[i][j].num == 0) continue;
			if (arr[i][j].sec == 1) arr[i][j].num = 0, arr[i][j].sec = 0;
			else arr[i][j].sec--;
		}
	}
	bool chk[21][21] = { false };
	for (int i = 0; i < tmp.size(); i++) { // 새 냄새 뿌리기
		x = tmp[i].x, y = tmp[i].y;
		if (!chk[x][y]) { // 번호가 더 작은 애가 차지한다
			chk[x][y] = true;
			arr[x][y].num = tmp[i].num, arr[x][y].sec = K;
		}
		else tmp[i].num = 0;
	}
	v.clear();
	for (int i = 0; i < tmp.size(); i++) { // 다음 이동을 위해 살아 있는 상어들 저장
		if (tmp[i].num != 0) v.push_back(SharkInfo(tmp[i].num, tmp[i].x, tmp[i].y, tmp[i].d));
	}
}

int main() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> n;
			if (n) {
				arr[i].push_back(SharkInfo(n, K));
				v.push_back(SharkInfo(n, i, j, 0));
			}
			else arr[i].push_back(SharkInfo(0, 0));
		}
	}

	sort(v.begin(), v.end()); // 작은 번호부터 정렬시키기 위해

	for (int i = 0; i < M; i++) cin >> v[i].d;
	for (int i = 1; i <= M; i++) for (int j = 1; j <= 4; j++) for (int k = 0; k < 4; k++) cin >> shark[i][j][k]; //상어 번호, 방향, 우선 순위

	while (1) {
		if ((int)v.size() == 1 && v[0].num == 1) break;
		if (res == 1000) {
			res++;
			break;
		}
		Move();
		res++;
	}

	if (res > 1000) cout << -1;
	else cout << res;
	return 0;
}

 

<괜히 우선 순위 큐 한번 써본 버전>

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

class info {
public:
	int num, x, y, dir, knum, k; // 현재 여기에 있는 상어 번호, x좌표, y좌표, 방향, 향기 주인 번호, 향기 남은 시간
	info() {}
	info(int num, int dir, int knum, int k) { this->num = num; this->dir = dir; this->knum = knum; this->k = k; }
	info(int num, int x, int y, int dir, int knum) { this->num = num; this->x = x; this->y = y; this->dir = dir; this->knum = knum; }
};

struct compare { // 상어 번호 기준 오름차순 정렬
	bool operator()(info a, info b) {
		return a.num > b.num;
	}
};

int N, M, K, res = -1;
int prior[401][5][5]; // [상어 번호][현재 방향][우선 순위]
int dx[5] = { 0, -1, 1, 0, 0 }, dy[5] = { 0, 0, 0, -1, 1 };
info arr[21][21];
priority_queue<info, vector<info>, compare > pq;


void moveShark() { // 상어 이동
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i][j].num == 0) continue; // 상어 없으면 넘어감
			bool moved = false;
			for (int m = 1; m <= 4; m++) { // [1] 아무 냄새가 없는 칸으로 가고자 함
				int dir = prior[arr[i][j].num][arr[i][j].dir][m]; // 가고자 하는 방향
				int x = i + dx[dir], y = j + dy[dir];
				if (x < 0 || x >= N || y < 0 || y >= N || arr[x][y].knum > 0) continue; // 범위를 벗어나거나 향기가 남아 있으면 못 감
				if (arr[x][y].num == 0 || arr[x][y].num > arr[i][j].num) { // 아무 상어도 없거나 있어도 자기가 번호 더 작으면 안 쫓겨남
					pq.push(info(arr[i][j].num, x, y, dir, arr[i][j].num));
					arr[i][j].num = arr[i][j].dir = 0; // 흔적 지우기
				}
				moved = true; // 첫트에 성공
				break;
			}
			if (moved) continue; // 첫트에 성공 못 하면 [2]로 넘어가야 함
			for (int m = 1; m <= 4; m++) { // [1] 아무 냄새가 없는 칸으로 가고자 함
				int dir = prior[arr[i][j].num][arr[i][j].dir][m]; // 가고자 하는 방향
				int x = i + dx[dir], y = j + dy[dir];
				if (x < 0 || x >= N || y < 0 || y >= N || arr[x][y].knum != arr[i][j].num) continue; // 범위를 벗어나거나 자기 향기가 아니면 못 감
				pq.push(info(arr[i][j].num, x, y, dir, arr[i][j].num));
				arr[i][j].num = arr[i][j].dir = 0; // 흔적 지우기
				break;
			}
		}
	}
}
bool updateSmell() { // 향기 남은 시간 조정, 새 향기 뿌리기
	int cnt = 0;
	while (!pq.empty()) {
		if (arr[pq.top().x][pq.top().y].num == 0) // 빈 칸일 경우에만 상어 배치한다. 아니면 나가리
			arr[pq.top().x][pq.top().y] = info(pq.top().num, pq.top().dir, pq.top().knum, K);
		pq.pop();
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i][j].num > 0) cnt++; // 남은 상어 수 세기
			else if (arr[i][j].k > 0) { // 시간 남은 향기가 있으면 시간 조정
				if (--arr[i][j].k == 0) arr[i][j].knum = 0; // k초 지난 향기는 흔적 없애기
			}
		}
	}
	return cnt == 1 ? true : false; // 한 마리(1번 상어) 남으면 true, 아니면 false
}

int main() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j].num;
			arr[i][j].knum = arr[i][j].num;
			arr[i][j].k = K; // 제일 먼저 자기 위치에 냄새 뿌리기
		}
	}
	int dir[401] = { 0 };
	for (int i = 1; i <= M; i++) cin >> dir[i];
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) arr[i][j].dir = dir[arr[i][j].num];
	for (int i = 1; i <= M; i++) for (int j = 1; j <= 4; j++) for (int k = 1; k <= 4; k++) cin >> prior[i][j][k];

	for (int i = 1; i <= 1000; i++) { // 최대 1000초
		moveShark();
		if (updateSmell()) {
			res = i;
			break;
		}
	}

	cout << res;
	return 0;
}