boj, 백준) 19237. 어른상어 ( C / C++)

1. 문제 링크

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

19237번: 어른 상어

2. 문제 개요

 상어에는 1에서 M이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

 

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

 

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

 

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

 

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

 

 

3. 문제 힌트

이런 시뮬레이션 문제 특성상 1가지 조건을 놓치거나 문제 이해를 잘못하면 어디서 틀렸지 하고 멘붕이 오기 마련이다..

 

문제를 풀면서 놓쳤던 부분을 힌트로 적어보면..

1. 현재 이동방향으로 이동하는 것이 아님. 이동방향에 따른 우선순위대로 이동하는 것입니다.

2. (초기) 상어 배치, 냄새 배치 -> 상어 이동 -> 냄새 카운트하기 -> 냄새 배치 이런 순서로 해야 합니다.

3. 상어 배열을 따로 관리하지 않고 맵에 숫자로 (1~M) 관리하게되면 이동할 때 이동한 상어가 한 번 더 움직일 수 있습니다.

 

이 정도라고 할 수 있다. 이 문제는 특별한 알고리즘이 필요한 것은 아니니까 문제를 잘 이해하고 N도 20x20으로 작은 데다가 잘 캐치하면 충분히 풀 수 있다고 생각한다.

 

그리고 냄새 배열과[N][N], 상어의 위치를 나타내는 배열[N][N] 2가지를 분리해서 관리하는 것이 프로그램 작성하는데 간단할 것이라고 생각합니다.

 

4. 문제 풀이

상어 구조체를 만들었다. y, x좌표, 그리고 각 방향에 따른 우선순위를 담을 배열, 살았는지 죽었는지 나타내는 bool변수.

 

상어 번호 값을 가지는 int map[20][20] 배열을 선언했고, 냄새를 관리하는 pair<int,int> smell[20][20]배열을 선언했다. 냄새 배열에는 누구의 냄새인지, 몇 초 뒤에 사라지는지, 를 나타내는 값을 가지고 있다.

 

그 외 값을 입력받고, 

시간이 1000초 보다 작은 동안 반복문을 실행한다.

 

여기서 이동하게 될 텐데,

1. 상어가 지금 바라보는 방향을 기준으로 우선순위대로 확인해본다.

  - 갈 수 있으면 이동.

  - 4방향 다 갈 수 없으면 한 번 더 4방향을 탐색하여 자기 냄새를 찾는다. 그리고 이동.

 

이동하는 경우는, map배열의 본인 번호를 0으로 바꾸고, Shark 배열의 본인의 좌표를 옮긴 뒤, 다음 좌표의 map배열에 상어 번호를 대입한다.

 

그리고 상어가 한 점에서 겹치는 경우 동시에 잡아먹으려고 생각하지 말고 그냥 겹칠 때마다 숫자가 낮은 상어가 살아남을 수 있도록 구현해주면 된다.

 

이동을 다 마쳤으면

냄새를 뿌리기 전에 기존의 냄새들의 시간을 1초씩 줄여주어야 한다. 냄새 배열을 전부 탐색하면서 주인이 있는 공간의 냄새들은 다 시간을 -1 해주고, 시간이 0 초면 냄새의 주인을 없애 빈칸처럼 나타내도록 하자.

 

 

이제는 냄새를 뿌릴차례이다. 냄새는 map배열을 훑으면서 0이 아닌 즉 상어가 존재하는 공간에 새로운 냄새를 뿌려주면 된다. 냄새의 주인은 map배열의 값이 될 테고, 시간은 k로 초기화해주면 된다.

 

마지막으로 shark배열을 탐색하거나 상어의 개수를 나타내는 변수를 만들어 1번빼고 모두 죽어있거나 혹은 상어가 1마리 남아있으면 그 상어는 1번 상어일 수밖에 없으므로 답을 출력하도록 하자.

 

 

5. 코드

#include <cstdio>
#include <algorithm>
using namespace std;

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

struct SHARK
{
	int y, x, dir;
	int order[5][5];
	bool isdead;
};

int n, m, k, ans = 1;
int map[20][20];
pair<int, int> smell[20][20];	//누구의 냄새, 남은 시간
SHARK shark[401];

int main()
{
	scanf("%d %d %d", &n, &m, &k);

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
		{
			scanf("%d", &map[i][j]);

			//상어 정보 입력
			if (map[i][j] != 0)
			{
				shark[map[i][j]].x = j;
				shark[map[i][j]].y = i;
				shark[map[i][j]].isdead = false;

				smell[i][j].first = map[i][j];
				smell[i][j].second = k;
			}
		}

	for (int i = 1; i <= m; ++i)
		scanf("%d", &shark[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", &shark[i].order[j][k]);

	while (ans <= 1000)
	{
		//이동
		for (int i = 1; i <= m; ++i)
		{
			if (shark[i].isdead)	continue;


			bool icango = false;
			for (int dir = 1; dir <= 4; ++dir)
			{
				//이동
				int nx = shark[i].x + dx[shark[i].order[shark[i].dir][dir]];
				int ny = shark[i].y + dy[shark[i].order[shark[i].dir][dir]];

				if (nx < 0 || ny < 0 || nx >= n || ny >= n || smell[ny][nx].first != 0)
					continue;
				
				//이 부분으로 오면 이동가능 함.
				icango = true;

				if (map[ny][nx] != 0)
				{
					//어떤 상어가 있는 경우
					if (map[ny][nx] < i)
					{
						//못 감.
						shark[i].isdead = true;
						map[shark[i].y][shark[i].x] = 0;
					}
					else
					{
						//상대방 죽음
						shark[map[ny][nx]].isdead = true;

						//갈 수 있음
						map[shark[i].y][shark[i].x] = 0;
						shark[i].x = nx;
						shark[i].y = ny;
						shark[i].dir = shark[i].order[shark[i].dir][dir];
						map[ny][nx] = i;
					}
				}
				else
				{
					//아무상어도 없는 경우.
					//갈 수 있음
					map[shark[i].y][shark[i].x] = 0;
					shark[i].x = nx;
					shark[i].y = ny;
					shark[i].dir = shark[i].order[shark[i].dir][dir];
					map[ny][nx] = i;
				}
				break;	//이동 했으니까 break
			}

			if (!icango)	//냄새로 둘러싸여 있어서 갈 수 없는경우
			{
				//내 냄새 찾기
				for (int dir = 1; dir <= 4; ++dir)
				{
					//이동
					int nx = shark[i].x + dx[shark[i].order[shark[i].dir][dir]];
					int ny = shark[i].y + dy[shark[i].order[shark[i].dir][dir]];

					if (nx < 0 || ny < 0 || nx >= n || ny >= n)
						continue;

					if (smell[ny][nx].first == i)
					{
						map[shark[i].y][shark[i].x] = 0;
						shark[i].x = nx;
						shark[i].y = ny;
						shark[i].dir = shark[i].order[shark[i].dir][dir];
						map[ny][nx] = i;
						break;
					}
				}
			}
		}
		//이동완료

		//냄새 제거
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				if (smell[i][j].first != 0)
				{
					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 (map[i][j] != 0)
				{
					smell[i][j].first = map[i][j];
					smell[i][j].second = k;
				}

		//1만 남았는지?
		//매번 m번의 반복을 하기 싫으면 상어의 수를 나타내어 1인지 확인해도 됨.
		//상어가 1마리가 남았을 때 1번임이 확실하기 때문.
		bool icanend = true;
		for (int i = 2; i <= m; ++i)
			if (shark[i].isdead == false)
			{
				icanend = false;
				break;
			}

		if (icanend)
		{
			printf("%d", ans);
			return 0;
		}
		else
		{
			ans++;
		}
	}
	printf("-1");
	return 0;
}

 

 

 

6. 결과

시간을 측정하면서 풀었기 때문에 조금 코드가 지저분할 수 있다. 더 빠르게 하면 0ms도 된다. 

 

 

지적 댓글 환영입니다!! :)