[ 백준-19237번 / 구현 ] 어른 상어

1. 문제

---

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 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 복사

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

문제에 나온 그림과 같다.

19237번: 어른 상어

 

2. 소스코드

---

1회차 - 2020/06/22

 

- 이 문제도 이전 청소년 상어문제와 같이,

(2020/06/18 - [알고리즘/PS] - [ 백준-19236번 / 완전탐색 / 구현 ] 청소년 상어)

자료구조를 어떻게 해야할 지 고민했다.

 

- 2개의 구조체를 사용했다.

 1번 째 구조체는 map에 정보를 표시한다. 자취를 남긴 상어의 번호(sNum), 자취의 남은 시간(timeout).

그리고 해당 위치에 상어를 넣어두는 queue를 만들었다.

queue를 이용한 이유는, 상어가 움직일때 다음 위치에는 넣어주고 이전 위치에서는 빼줘야하기 때문. 큐를 사용하지 않으면, FIFO가 되지 않아서 이전 위치에서 뺄때 단순히 pop으로 처리할 수 없었다.

 하지만 queue를 사용하기 때문에, 나중에 같은 칸에 여러마리의 상어가 있는 경우를 처리할때 시간이 오래걸린다. queue에 있는 상어의 숫자를 하나하나 비교해줘야하기 때문. 개선해야할 점 인것 같다.

struct Area
{
	int sNum, timeout;
	queue<int> sharks;
};
Area map[MAX][MAX];

 

- 두 번째 구조체는 상어의 정보를 저장한다.

struct Info
{
	int x, y, dir;
	int prior[5][5];
};
vector<Info> sharkPos;

- 상어의 정보를 map에 저장해두면, 움직이거나 자취를 남길때 시간이 오래걸리기 때문에 따로 자료구조를 만들었다.

 

 

- 전체적인 로직은 다음과 같다.

1) 상어의 자취를 남긴다. 반드시 동시에 해야함.

2) 상어를 규칙에 따라 움직인다.

3) map을 순회하면서 자취의 시간을 감소시키고, 같이 있는 상어들을 처리한다.

 

소스코드

#include <cstdio>
#include <vector>
#include <queue>
#define MAX 20
#define OUT -1
using namespace std;

struct Area
{
	int sNum, timeout;
	queue<int> sharks;
};
Area map[MAX][MAX];
struct Info
{
	int x, y, dir;
	int prior[5][5];
};
vector<Info> sharkPos;

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

int n, m, k;
  
int simulation() {

	for (int time = 0; time <= 1000; ++time) {
		
		// 상어가 1마리만 남은 경우 종료
		if (m == 1) { 
			return time; 
		}

		// 1) 상어의 자취를 남긴다. 동시에 해야함.
		for (int i = 1; i < sharkPos.size(); ++i) {
			int x = sharkPos[i].x;
			int y = sharkPos[i].y;
			if (x == OUT and y == OUT) continue;

			map[x][y].sNum = i;
			map[x][y].timeout = k;
		}
		// 2) 상어를 규칙에 따라 동시에 움직임
		for (int i = 1; i < sharkPos.size(); ++i) {
			int x = sharkPos[i].x;
			int y = sharkPos[i].y;
			if (x == OUT and y == OUT) continue;

			int dir = sharkPos[i].dir;
 
			bool moved = false;
			int promiseX = -1, promiseY = -1, promiseDir;
			while (promiseX == -1)
			{
				for (int j = 1; j <= 4; j++) {
					int nextDir = sharkPos[i].prior[dir][j];
					int nx = x + dx[nextDir];
					int ny = y + dy[nextDir];

					if (nx >= n or ny >= n or nx < 0 or ny < 0) continue;
					//내 자취를 발견한 경우.
					if (!moved and promiseX == -1 and map[nx][ny].sNum == i) {
						//일단 유망한 위치로 set
						promiseX = nx;
						promiseY = ny;
						promiseDir = nextDir;
					}

					if (!moved and map[nx][ny].sNum) continue;
					//아예 빈칸을 발견한경우 기존 유망한 위치를 덮어씀
					promiseX = nx;
					promiseY = ny;
					promiseDir = nextDir;
					moved = true;
					break;
				}
				if (promiseX != -1) {
					map[promiseX][promiseY].sharks.push(i);
					map[x][y].sharks.pop();
					sharkPos[i].x = promiseX;
					sharkPos[i].y = promiseY;
					sharkPos[i].dir = promiseDir;
				}
				else break;
			}

		}

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {

				//3) map의 자취 전부 -1
				if (map[i][j].timeout) map[i][j].timeout--;
				if (map[i][j].timeout == 0) map[i][j].sNum = 0;

				//4) 겹치는 상어를 처리.
				if (map[i][j].sharks.size() > 1) {
					int cur = map[i][j].sharks.front();
					map[i][j].sharks.pop();

					while (!map[i][j].sharks.empty())
					{
						int next = map[i][j].sharks.front();
						map[i][j].sharks.pop();
						if (cur > next) swap(cur, next);
						sharkPos[next].x = OUT;
						sharkPos[next].y = OUT;
						m--;
					}
					map[i][j].sharks.push(cur);
				}
			}
		}// end of 3 and 4
	}
	return -1;
}

int main() {

	scanf("%d %d %d", &n, &m, &k);
	sharkPos.resize(m + 1);// 0번 상어는 비워둔다. 상어의 숫자만큼

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			int temp;
			scanf("%d", &temp);
			if (temp) {
				sharkPos[temp] = { i,j };
				map[i][j].sharks.push(temp);
			}
		}
	//상어의 초기 방향을 받는다.
	for (int i = 1; i <= m; ++i)
		scanf("%d", &sharkPos[i].dir);

	//상어별 우선순위를 저장한다.
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= 4; ++j)
			for (int k = 1; k <= 4; ++k)
				scanf("%d", &sharkPos[i].prior[j][k]);

	printf("%d", simulation());

	return 0;
}