백준 19237번 : 어른 상어 (c++)

www.acmicpc.net/problem/19237

19237번: 어른 상어

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

입력

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

예제 입력 1 
5 4 4
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3
예제 출력 1 
14

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>

using namespace std;
int N, M, k;
int time = 0;
int dy[] = {0,-1,1,0,0 };
int dx[] = {0,0,0,-1,1 };
struct shark {
	int y, x, d;
};
struct info {
	int shark;
	int timeLeft;
};
info map[20][20];
shark sharks[401];
int preferMove[401][5][5];
bool chking[401];

bool isOk() {
	for (int i = 2; i <= M; i++)
	{
		if (!chking[i]) {
			return true;
		}
	}
	return false;
}

void move() {
	//1초

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (map[i][j].timeLeft > 0) {
				map[i][j].timeLeft--;
			}
		}
	}

	for (int i = 1; i <= M; i++)
	{
		if (chking[i])	continue;
		int y = sharks[i].y;
		int x = sharks[i].x;
		int d = sharks[i].d;
		int nowState = 0;
		for (int j = 1; j <= 4; j++)
		{
			int ny = y + dy[preferMove[i][d][j]];
			int nx = x + dx[preferMove[i][d][j]];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N)	continue;
			if (map[ny][nx].shark != 0) continue;
			nowState = 1;
			sharks[i].y = ny;
			sharks[i].x = nx;
			sharks[i].d = preferMove[i][d][j];
			break;
		}
		if (nowState == 0) {
			for (int j = 1; j <= 4; j++)
			{
				int ny = y + dy[preferMove[i][d][j]];
				int nx = x + dx[preferMove[i][d][j]];
				if (ny < 0 || nx < 0 || ny >= N || nx >= N)	continue;
				if (map[ny][nx].shark == i) {
					sharks[i].y = ny;
					sharks[i].x = nx;
					sharks[i].d = preferMove[i][d][j];
					break;
				}
			}
		}

	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (map[i][j].timeLeft == 0) {
				map[i][j].shark=0;
			}
		}
	}

	for (int i = 1; i <= M; i++)
	{
		if (chking[i])	continue;
		int y = sharks[i].y;
		int x = sharks[i].x;
		if (map[y][x].timeLeft == k) {
			chking[i] = true;
			continue;
		}
		map[y][x].shark = i;
		map[y][x].timeLeft = k;
	}
}


int main() {
	freopen("input.txt", "r", stdin);
	cin >> N >> M >> k;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int a;
			cin >> a;
			if (a != 0) {
				sharks[a] = { i,j,0 };
				map[i][j] = { a,k };
			}
		}
	}

	for (int i = 1; i <= M; i++)
	{
		cin>>sharks[i].d;
	}

	for (int i = 1; i <= M; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			for (int k = 1; k <= 4; k++)
			{
				cin>>preferMove[i][j][k];
			}
		}
	}

	while (isOk()) {
		time++;
		if (time > 1000) {
			time = -1;
			break;
		}
		move();
	}
	cout << time;
	return 0;
}