[백준/BOJ] 백준 19237번 : 어른 상어

www.acmicpc.net/problem/19237

19237번: 어른 상어

smell_board[20][20]에 각 칸의 냄새 정보를 저장하는 것을 만들고 shark_info[401]에 각 상어의 정보를 저장하는 것을 만들었다 여기서 사라진 상어는 { -1,-1,-1 }로 표현하였다. 그리고 vector<int> priority_dir[401][5] 에 어떤 상어가 어떤 방향일때 움직이는 곳의 우선순위를 순서대로 저장하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

struct smell {
	int remain; //냄새나 남아있는 시간
	int number; //냄새를 뿌린 상어의 번호
};

struct shark {
	int x;
	int y;
	int dir;
};

int n, m, k;
smell smell_board[20][20];
shark shark_info[401];
int dxdy[5][2] = { {0,0},{-1,0},{1,0},{0,-1},{0,1} };
vector<int> priority_dir[401][5]; //어떤 상어가 어떤 방향일때 움직이는 곳의 우선순위 저장

void Pre()
{
	for (int i = 0; i < 20; i++)
		for (int j = 0; j < 20; j++)
			smell_board[i][j] = { 0,0 };
}

//냄새 뿌리기
void Make_smell()
{
	for (int i = 1; i <= m; i++)
	{
		shark this_shark = shark_info[i];

		//사라진 상어일때
		if (shark_info[i].x == -1 && shark_info[i].y == -1 && shark_info[i].dir == -1)
			continue;

		smell_board[this_shark.x][this_shark.y] = { k,i };
	}
}

//냄새 카운트 1 다운
void Down_smell()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (smell_board[i][j].number > 0)
			{
				smell_board[i][j].remain--;

				if (smell_board[i][j].remain == 0)
					smell_board[i][j] = { 0,0 };
			}
		}
}

//1번 상어만 남아있는지 확인
bool Check()
{
	for (int i = 1; i <= m; i++)
	{
		if (i == 1)
			continue;

		if (shark_info[i].x != -1 && shark_info[i].y != -1 && shark_info[i].dir != -1)
			return false;
	}

	return true;
}

void Move()
{
	set<int> board[20][20];
	set<int>::iterator it;

	for (int i = 1; i <= m; i++)
	{
		shark this_shark = shark_info[i];

		//사라진 상어일때
		if (this_shark.x == -1 && this_shark.y == -1 && this_shark.dir == -1)
			continue;

		bool there_find = false;
		for (int j = 0; j < 4; j++)
		{
			int temp_dir = priority_dir[i][this_shark.dir][j]; //가장 우선순위인 방향부터 확인
			shark there_shark = { this_shark.x + dxdy[temp_dir][0] , this_shark.y + dxdy[temp_dir][1], temp_dir };

			if (there_shark.x >= 0 && there_shark.x < n && there_shark.y >= 0 && there_shark.y < n && smell_board[there_shark.x][there_shark.y].number == 0)
			{
				there_find = true;
				shark_info[i] = there_shark;
				break;
			}
		}

		if (there_find == false) //냄새가 없는곳이 없을때 (갈 수 있는 방향을 위에서 찾지 못했을때)
		{
			for (int j = 0; j < 4; j++)
			{
				int temp_dir = priority_dir[i][this_shark.dir][j];
				shark there_shark = { this_shark.x + dxdy[temp_dir][0] , this_shark.y + dxdy[temp_dir][1], temp_dir };

				if (there_shark.x >= 0 && there_shark.x < n && there_shark.y >= 0 && there_shark.y < n && smell_board[there_shark.x][there_shark.y].number == i) //자신이 뿌린 냄새 방향 확인
				{
					there_find = true;
					shark_info[i] = there_shark;
					break;
				}
			}
		}

		//board에 상어 움직임 표현
		board[shark_info[i].x][shark_info[i].y].insert(i);
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			//해당 위치에 가장 작은 번호의 상어만 남긴다
			if (board[i][j].size() > 1)
			{
				it = board[i][j].begin();
				it++;

				for (; it != board[i][j].end(); it++)
				{
					shark_info[*it] = { -1,-1,-1 };
				}
			}
		}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n >> m >> k;

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

			if (input != 0)
			{
				shark_info[input] = { i,j,0 }; //상어 위치 정보 저장
			}
		}

	for (int i = 1; i <= m; i++)
	{
		int input;
		cin >> input;

		shark_info[i].dir = input; //상어 방향 정보 저장
	}

	for (int i = 1; i <= m; i++) //어떤 상어가
	{
		for (int j = 1; j <= 4; j++) //어떤 방향일때
		{
			for (int k = 1; k <= 4; k++) //우선순위
			{
				int input;
				cin >> input;

				priority_dir[i][j].push_back(input);
			}
		}
	}

	int result = 0;
	while (1)
	{
		Make_smell(); //냄새 뿌리기
		Move(); //움직이기
		Down_smell(); //냄새 카운트 1 다운

		result++;

		if (result > 1000) //1000초가 넘을때
		{
			result = -1;
			break;
		}

		if (Check()) //1번 상어만 남았는지 확인
			break;
	}

	cout << result;

	return 0;
}