[백준/c++] 19237 어른 상어

문제

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

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

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

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

<그림 1>

<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.

<그림 2>

<그림 3>

<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.

<그림 4>

<그림 5>

<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.

이 과정을 반복할 때, 13) 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

입력

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

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

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

출력

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

구현해야할 조건

상어는 영역을 차지하기 위해 다른 상어를 쫓아내게되는데 1의 번호를 가진 상어는 가장 강력하다.
상어는 이동하기 전에 자신의 위치에 자신의 냄새를 뿌린후, 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동을 하게 되며, 자신의 냄새를 그 칸에 뿌립니다. 냄새는 상어가 k번 이동하고 나면 사라지게 됩니다.

각 상어의 이동방향은 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡습니다.(우선순위 방향으로) 그러한 칸이 없다면 자신의 냄새가 있는 칸의 방향으로 잡습니다.(우선순위 방향으로) 이점을 유의해야 한다. 초반에 그냥 4방향 따지고 우선순위로 이동하려고 했는데, 그것이 아니고 처음부터 우선순위로 따지는 것이다.

가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓아낸다.

 

code

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

#define MAX 21
using namespace std;

typedef struct{
	int y;
	int x;
	int number;
	int dir;
}Shark;

const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0}; // up, down, left, right 

Shark s[MAX*MAX];

int n,m,k;
int board[MAX][MAX];
int priority[MAX*MAX][5][5];
pair<int,int> smell[MAX][MAX];

bool comp(pair<int,int> &a, pair<int,int> &b)
{
	return a.first < b.first; // 가장 숫자가 작은 상어를 구하기 위해서 
}

int main()
{	
	cin >> n >> m >> k;
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cin >> board[i][j];
			
			if(1 <= board[i][j]) // 1이상인 상어들 
			{
				s[board[i][j]].y = i;
				s[board[i][j]].x = j;
				s[board[i][j]].number = board[i][j];
				smell[i][j] = {board[i][j],k}; // 냄새를 새겨야하니까 상어의 위치마다 
			}
		}
	}
	
	for(int i = 1; i <= m; i++)
	{
		int direction;
		cin >> direction;
		s[i].dir = direction - 1;  
	}
	
	for(int i = 1; i <= m; i++)
	{
		for(int j = 0; j < 4; j++)
		{
			for(int k = 0; k < 4; k++)
			{
				int pri_direction;
				cin >> pri_direction;
				priority[i][j][k] = pri_direction-1;
			}
		}
	}
	
	queue<Shark> q;
	
	for(int i = 1; i <= m; i++)
		q.push({s[i]}); // q에 집어넣기 
	
	int time = 0;
	
	while(1)
	{
		if(time > 1000)
		{
			cout << -1;
			return 0;
		}
				
		if(q.size() == 1) // 1만 남게되면 멈추자 
			break;
			
		vector<pair<int,int> > sharks[MAX][MAX];
			
		while(!q.empty())
		{
			//냄새 제거 하는 방식이 필요하다. 
			int y = q.front().y;
			int x = q.front().x;
			int dir = q.front().dir;
			int num = q.front().number;
			q.pop();

			bool chk = false;// 냄새없는 곳 체크
			
			for(int i = 0; i < 4; i++)
			{
				int nx = x + dx[priority[num][dir][i]];
				int ny = y + dy[priority[num][dir][i]];
				
				if(0 <= nx && nx < n && 0 <= ny && ny < n && smell[ny][nx].second == 0)
				{
					sharks[ny][nx].push_back({num,priority[num][dir][i]}); // 2차원 벡터 배열에 먼저 넣어줘야 한다. 상어가 겹칠 수 있기 때문에
					//queue를 먼저 넣어주게 되면 겹쳐진 애들을 관리하지 못한다.
					// smell 도 마찬가지 
					chk = true;
					break;
				}
			}
			// chk == false 냄새 안나는 곳이 없다. 냄새가 전부 난다 !!! 
			if(!chk) 
			{
				for(int i = 0; i < 4; i++)
				{
					int nx = x + dx[priority[num][dir][i]];
					int ny = y + dy[priority[num][dir][i]];
					
					if(0 <= nx && nx < n && 0 <= ny && ny < n && smell[ny][nx].first == num) // 자신의 번호가 적혀있는 곳으로 우선순위를 둔다. 
					{
						sharks[ny][nx].push_back({num,priority[num][dir][i]}); // 이것도 마찬가지로 
						break;
					}
				} 
			}
		}
		//sharks에 넣어줬을 때, sort해주고, smell에도 넣어주고 미리 넣어주면 값이 바뀌니까 
		// 이동이 되었다면 냄새를 한번씩 지워주게 된다. 
		
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(smell[i][j].second)
				{
					smell[i][j].second--;// 기존에 있던 냄새 제거 
					
					if(smell[i][j].second == 0) // 냄새가 완전히 사라졌다? 
					{
						smell[i][j].first = 0; 
					}
				}
			}
		}
			
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(sharks[i][j].size() > 1)
				{
					sort(sharks[i][j].begin(),sharks[i][j].end(),comp); // 작은 숫자로 정렬을 해주고 
					smell[i][j] = {sharks[i][j][0].first, k}; // smell에 넣어주고, number와 k 냄새의 양 
					q.push({i,j,sharks[i][j][0].first,sharks[i][j][0].second}); // queue에 다시 넣어주기 
				}
				else if(sharks[i][j].size() == 1) // 하나라면 sort해줄 필요 없음! 
				{
					smell[i][j] = {sharks[i][j][0].first, k};
					q.push({i,j,sharks[i][j][0].first,sharks[i][j][0].second});
				}
			}
		}

		time++;
	}
	
	
	cout << time;
	
	
	return 0;
}