[C/C++] 백준 - 19237번 : 어른 상어

https://www.acmicpc.net/problem/19237

19237번: 어른 상어

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.
N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.
각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.
모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

<그림 1>
우선 순위상어 1상어 2상어 3상어 4↑↑↑↑↓↓↓↓←←←←→→→→

↓ ← ↑ →	↓ → ← ↑	→ ← ↓ ↑	← → ↑ ↓
→ ↑ ↓ ←	↓ ↑ ← →	↑ → ← ↓	← ↓ → ↑
← → ↓ ↑	← → ↑ ↓	↑ ← ↓ →	↑ → ↓ ←
→ ← ↑ ↓	→ ↑ ↓ ←	← ↓ ↑ →	↑ → ↓ ←

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

<그림 2>

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

<그림 4>

<그림 5>
<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.
이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 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번 상어만 격자에 남게 되기까지 걸리는 시간

< 사용한 자료구조 및 알고리즘 >
이 문제에서는 큐 자료구조를 사용하여 상어의 각 위치를 초기화 시켰고, 상어의 냄새가 있는 칸은 덱을 이용하여 냄새가 있는 좌표와 남은 시간을 관리하였으며, 벡터를 이용하여 각 방향에 따른 우선순위 방향좌표를 저장해주었다.

map은 구조체 형식으로
상어의 번호 (0은 상어가 존재하지 않는 칸)
시간 (상어의 냄새가 없어지기까지의 시간)
방향 (상어가 존재한다면 상어가 현재 바라보는 방향)
bool형태의 minus(상어가 존재한다면 냄새의 시간을 줄일지 말지 정해주는 변수)
-> 상어의 이동이 끝난 후 상어의 냄새가 있던 칸은 시간이 1만큼 줄어든다. 하지만 방금 이동한 좌표는 시간이 줄어들지 않고 전에 냄새가 있던 칸들만 시간이 줄어든다. 이것을 구분하기 위해 bool형태의 변수를 통해 결정해주었다.

전에 올렸었던 원판 돌리기 문제처럼 이 문제 또한 같은 map에서 상어의 번호, 냄새 없어지기까지 남은 시간 등 계속해서 최신화 해주어야 하는 변수들이 존재한다. 그렇기에 값을 저장해주고 그 저장된 값을 기준으로 최신화 할지 말지 결정해주는 또 다른 map을 선언해주어야한다.

상어는 어처피 최신화가 계속 되더라도 각 1마리만 존재할 수 있다. 그렇기에 큐도 각 idx를 가지는
queue<int> q[403] 형태로 선언해주었다.

이제 문제에서 하라는대로 각 상어의 번호 순대로 이동을 결정해야한다.

1. 상어 위치에서 인접한 곳에 갈 수 있는 곳이 존재하는지 확인해준다
-> 여기서도 상어가 바라보는 방향에 따른 우선순위 조건에 만족하도록 해주어야한다.
-> 만약 상어가 갈 수 있는 곳이 존재한다면, 그 위치에 다른 상어가 존재할 수도 있다. 이 때 상어의 번호를 확인해주어, 이미 위치해있는 상어의 번호가 더 크면 그 상어는 밖으로 나가게하고 해당 상어가 들어가야한다.
그러나 이미 위치해있는 상어 번호가 더 작으면 방향을 확인하는 해당 상어는 들어갈 수 없다
이런 경우 각 경우에 따라 큐를 비워줘야하는 경우가 생긴다. 여기에서 헷갈렸다.
-> 만약 상어가 갈 수 있는 곳이 존재하고, 그 칸이 비어있다면 그 곳으로 이동시켜주면 된다. 그리고 전에 좌표는 모든 상어의 이동이 끝난 후 냄새의 남은 시간을 줄여주어야 한다.

2. 만약 상어가 인접한 곳에 갈 수 있는 곳이 존재하지 않는다면 자신의 냄새가 있는 칸으로 이동해야한다
-> 여기서도 마찬가지로 자신이 바라보고 있는 방향에 따른 우선순우 조건에 만족하도록 이동시켜주면된다.

1,2번을 통해 상어를 이동시켜주었으면 방금 이동한 상어의 위치만 bool변수를 true로 바꿔준다.
그 이유는 아까 말했듯 방금 이동한 좌표를 제외하고 나머지 위치에 상어의 냄새가 존재한다면 그 시간을 줄여주어야하기 때문이다.
위 과정으로 방금 이동한 좌표를 제외하고 다른 좌표에 존재하는 상어의 냄새 시간을 모두 줄여준다.

위 과정을 반복해서 하다보면 위에 빨간줄에 의해 상어가 1번을 제외하고 모두 튕겨져 나가거나, 경로가 겹치지 않으면 1000번이 넘도록 1번을 제외한 다른 상어가 계속 맵에 존재할 수 있다.

1번 상어만 남는 경우까지 걸리는 시간, 만약 1000번이 넘도록 1번 상어 외 다른 상어가 존재한다면 -1을 출력해주면 된다

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 9876543210
using namespace std;

typedef long long ll;
typedef pair<int, int> pl;

// BOJ :: https://www.acmicpc.net/problem/17822

//맨 처음 모든 상어가 자신의 위치의 냄새를 뿌림
//그 후 1초마다 모든 상어가 동시에 상화좌우로 인접한 칸 중 하나로 이동, 자신의 냄새를 그 칸에 뿌린다.
//냄새는 상어가 k번 이동하고 나면 사라짐
//
//각 상어가 이동방향을 결정하는 우선순위
//1. 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다.
//2. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다
//->이 때, 가능한 칸이 1개가 아닐 수 있는데, 그 경우에는 또 다른 특정한 우선순위를 따른다
//특정한 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 다를 수 있다
//
//모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두
//격자 밖으로 쫓겨난다.
//
//위 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램

struct infor {
	int sec;
	int shark_N;
	int Direct;
	bool minus;
};

int N, M, K, Answer;
infor adj[22][22];
infor copy_adj[22][22];
deque<pair<int,pair<int,int>>> v[403]; // 상어의 남은 시간, 좌표
vector<int> Direct_Information[403][10];    // 각 상어 방향의 우선순의
queue<pair<int, int>> q[403];			// 상어 번호에 따른 좌표

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

void Input_Data() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			// Map에는 0과 상어의 번호가 입력됨
			cin >> adj[i][j].shark_N;
			adj[i][j].minus = false;
			// 입력받은 변수가 0이 아닌 경우에는 상어에 해당
			if (adj[i][j].shark_N != 0) {
				// 초기 상어의 남은 시간은 입력받은 시간K가 된다.
				adj[i][j].sec = K;
				// 이 정보를 벡터에 넣어주며 벡터에는 남은 시간, 상어의 좌표가 들어가게 된다.
				// 어처피 상어가 이동할 때 뒤에서 넣어주는 것이므로 벡터 안에 상어의 남은 시간은 오름차순으로 저장된다
				v[adj[i][j].shark_N].push_back(make_pair(K, make_pair(i, j)));
				// 상어는 맵에 한마리씩 밖에 존재하지 않는다. 상어의 좌표를 큐에 넣어준다.
				q[adj[i][j].shark_N].push(make_pair(i, j));
			}
		}
	}
	for (int i = 1; i <= M; i++) {
		int dir; cin >> dir;
		int y = v[i].front().second.first;
		int x = v[i].front().second.second;
		// 상어의 초기 바라보는 방향을 지정
		adj[y][x].Direct = dir;
	}

	for (int i = 1; i <= M; i++) {
		for (int d = 1; d <= 4; d++) {
			for (int p = 0; p < 4; p++) {
				int pr; cin >> pr;
				Direct_Information[i][d].push_back(pr);
			}
		}
	}

}

int isValid(int y, int x) {
	return (0 <= y && y < N && 0 <= x && x < N);
}

bool is_OnlyIn() {
	bool ok = false;
	bool is = false;
	for (int i = 1; i <= M; i++) {
		if (i == 1) {
			if (!q[i].empty()) ok = true;
		}
		else {
			if (!q[i].empty()) is = true;
		}
	}
	if (ok == true && is == false) return true;
	return false;
}

void Copy() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			copy_adj[i][j].shark_N = adj[i][j].shark_N;
			copy_adj[i][j].Direct = adj[i][j].Direct;
			copy_adj[i][j].sec = adj[i][j].sec;
		}
	}
}

void Erase_Smell() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (adj[i][j].sec == 0) continue;
			if (adj[i][j].minus == true) continue;
			adj[i][j].sec--;
			if (adj[i][j].sec == 0) {
				adj[i][j].shark_N = 0;
				adj[i][j].Direct = 0;
			}
		}
	}
}

int Solve_Shark_Move() {
	while (1) {
		if (Answer > 1000) return -1;
		if (is_OnlyIn()) break;

		Copy();
		for (int i = 1; i <= M; i++) {
			if (q[i].empty()) continue;
			int y = q[i].front().first;
			int x = q[i].front().second;
			q[i].pop();
			adj[y][x].minus = false;

			int curDir = adj[y][x].Direct;
			bool isCan = false;
			for (int k = 0; k < 4; k++) {
				int nextY = y + dy[Direct_Information[i][curDir][k]];
				int nextX = x + dx[Direct_Information[i][curDir][k]];

				if (isValid(nextY, nextX)) {
					if (!copy_adj[nextY][nextX].shark_N) {
						isCan = true;
						if (adj[nextY][nextX].shark_N != 0) {
							if (i < adj[nextY][nextX].shark_N) {
								// 이미 안에 다른 상어가 있지만, 번호가 더 큰 상어일 경우 없애버림
								q[adj[nextY][nextX].shark_N].pop();
								v[adj[nextY][nextX].shark_N].pop_back();

								adj[nextY][nextX].shark_N = i;
								adj[nextY][nextX].Direct = Direct_Information[i][curDir][k];
								adj[nextY][nextX].sec = K;
								adj[nextY][nextX].minus = true;
								q[i].push(make_pair(nextY, nextX));
							}
							else break;					
						}
						else {
							adj[nextY][nextX].shark_N = i;
							adj[nextY][nextX].Direct = Direct_Information[i][curDir][k];
							adj[nextY][nextX].sec = K;
							adj[nextY][nextX].minus = true;
							q[i].push(make_pair(nextY, nextX));
						}
					}
				}
				if (isCan) break;
			}

			// 자신의 냄새가 있는 칸으로 이동해야하는 경우
			if (!isCan) {
				for (int k = 0; k < 4; k++) {
					int nextY = y + dy[Direct_Information[i][curDir][k]];
					int nextX = x + dx[Direct_Information[i][curDir][k]];

					if (isValid(nextY, nextX)) {
						if (copy_adj[nextY][nextX].shark_N == i) {
							q[i].push(make_pair(nextY, nextX));
							adj[nextY][nextX].shark_N = i;
							adj[nextY][nextX].Direct = Direct_Information[i][curDir][k];
							adj[nextY][nextX].sec = K;
							adj[nextY][nextX].minus = true;
							isCan = true;
						}
					}
					if (isCan) break;
				}
			}
		}
		Erase_Smell();

		Answer++;
	}
	return Answer;
}

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

	Input_Data();
	cout << Solve_Shark_Move() << '\n';
	
	return 0;
}