[백준/BOJ] 백준 16236번 : 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

상어의 정보를 따로 저장해 놓는다. Search()를 통해 가장 가까운 물고기를 먹는데, 먹을 수 있는 거리가 가장 가까운 물고기가 많을 때를 위해 우선, 거리가 가장 가까운 물고기 들을 모두 저장해 놓은 뒤 가장 위에, 가장 왼쪽 우선순위로 정렬을 한 뒤 가장 앞의 물고기를 먹는다 그리고 Search()는 물고기를 먹는데 걸린 시간을 반환한다 이때 먹을 수 있는 물고기가 없을때 -1을 반환하며 이때부터 더 이상 Search()를 하지 않는다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

int n;
int board[20][20];
int dxdy[4][2] = { {-1,0},{0,-1},{0,1},{1,0} };
pair<int, int> shark;
int shark_size = 2;
int shark_eat = 0;

int Search()
{
	vector<vector<int>> discovered(n, vector<int>(n, 0));
	vector<vector<int>> depth(n, vector<int>(n, 0));
	discovered[shark.first][shark.second] = 1;
	depth[shark.first][shark.second] = 0;

	queue<pair<int, int>> q;
	q.push(shark);

	vector<pair<int, int>> temp; //먹을 물고기 후보들을 저장
	int temp_depth = 987654321;

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//먹을 수 있는 물고기를 찾았을때
		if (board[here.first][here.second] != 0 && board[here.first][here.second] < shark_size)
		{
			if (depth[here.first][here.second] <= temp_depth)
			{
				temp.push_back(here); //먹을 물고기 후보에 저장
				temp_depth = depth[here.first][here.second];
				continue;
			}

			//먹을 수 있는 물고기를 찾았지만 후보 물고기들 보다 먼 물고기일때
			else
				break;
		}

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && discovered[there.first][there.second] == 0 && board[there.first][there.second] <= shark_size)
			{
				discovered[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;

				q.push(there);
			}
		}
	}

	//먹을 수 있는 물고기가 없을때
	if (temp.size() == 0)
		return -1;

	sort(temp.begin(), temp.end());//먹을 수 있는 거리가 가까운 물고기가 많을때 가장 위에, 가장 왼쪽 우선순위로 정렬
	
	board[temp[0].first][temp[0].second] = 0; //temp[0]물고기를 먹는다
	shark = temp[0];
	shark_eat++;

	//자신의 크기와 같은 수의 물고기를 먹었을때
	if (shark_eat == shark_size)
	{
		shark_size++;
		shark_eat = 0;
	}

	return depth[shark.first][shark.second];
}

int Solve()
{
	int ret = 0;

	while (1)
	{
		int day = Search();

		//먹을 수 있는 물고기가 없을때
		if (day == -1)
			break;

		else
			ret += day;
	}

	return ret;
}

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

	int input;

	cin >> n;

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

			if (input == 9)
			{
				shark = make_pair(i, j); //상어의 위치는 따로 저장
				board[i][j] = 0; //상어의 위치는 board에 0으로 표현
			}

			else
				board[i][j] = input;
		}
	}

	cout << Solve();

	return 0;
}