[백준 C++] 16236 아기 상어 - 너비우선탐색

16236번: 아기 상어

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int, int> p;
typedef pair<pair<int, int>, int> pp;

const int DX[4] = { -1, 0, 1, 0 };
const int DY[4] = { 0, -1, 0, 1 };

int N;
int Bowl[20][20];
bool Visited[20][20];

int Time, Ate;
int Size = 2;
int Row, Col;

bool Target(int R, int C, int D, int FR, int FC, int FD)
{
	if (Bowl[R][C] < Size
		&& Bowl[R][C] != 0
		&& D <= FD
		&& ((R < FR) || (R == FR && C < FC)))
	{
		return true;
	}

	return false;
}

pp BFS()
{
	memset(Visited, false, sizeof(Visited));

	int FR = N;
	int FC = N;
	int FD = 1000;

	queue<pp> SQ;
	Visited[Row][Col] = true;
	SQ.emplace(p(Row, Col), 0);
	while (!SQ.empty())
	{
		int R = SQ.front().first.first;
		int C = SQ.front().first.second;
		int D = SQ.front().second;
		SQ.pop();

		for (int i = 0; i < 4; ++i)
		{
			int NR = R + DY[i];
			int NC = C + DX[i];
			if (NR < 0 || NR > N - 1 || NC < 0 || NC > N - 1
				|| Visited[NR][NC] || Bowl[NR][NC] > Size)
			{
				continue;
			}

			Visited[NR][NC] = true;
			if (Target(NR, NC, D + 1, FR, FC, FD))
			{
				FR = NR;
				FC = NC;
				FD = D + 1;
			}
			else
			{
				SQ.emplace(p(NR, NC), D + 1);
			}
		}
	}

	return pp(p(FR, FC), FD);
}

bool EatFish()
{
	pp Min = BFS();
	if (Min.second == 1000)
	{
		return false;
	}

	Bowl[Row][Col] = 0;

	Row = Min.first.first;
	Col = Min.first.second;
	Bowl[Row][Col] = 9;
	Time += Min.second;

	++Ate;
	if (Ate == Size)
	{
		Ate = 0;
		++Size;
	}

	return true;
}

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

	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> Bowl[i][j];
			if (Bowl[i][j] == 9)
			{
				Row = i;
				Col = j;
			}
		}
	}

	while (EatFish()) {}
	cout << Time;
}

---

 

시뮬레이션 & BFS 문제입니다.

아기 상어가 먹이를 더이상 먹을 수 없을 때까지 먹이를 찾고 먹는 행동을 반복하도록 해야 합니다.

풀이 과정은 다음과 같습니다.

 

1. 너비 우선 탐색을 이용해 가장 가까운 먹이 탐색 및 선택

1-a. 먹이는 상어보다 크기가 작아야 함

1-b. 거리가 같은 먹이가 여러개면 위쪽, 왼쪽 위치 순으로 우선 선택

2. 목표로 지정한 먹이의 위치로 상어 이동

3. 시간 증가 및 누적 먹이량에 따른 상어 크기 조정