아기 상어 (feat. 백준, 16236번)

아기 상어
https://www.acmicpc.net/problem/16236

16236번: 아기 상어

반응형

// woohyeon.kim
#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> eat_lists;
int arr[21][21] = { 0 };
int node[21][21] = { 0 };
bool visit[21][21] = { false };
int N;
int eat_count;
int shark_size;
int total_time;

bool bfs(pair<int, int>& now)
{
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < N; ++iy)
		{
			visit[ix][iy] = false;
			node[ix][iy] = 0;
		}
	}

	node[now.first][now.second] = 1;
	int dx[] = {1, -1, 0, 0};
	int dy[] = {0, 0, -1, 1};

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

	pair<int, int> point, tmp;
	while (!q.empty())
	{
		point = q.front(); q.pop();
		visit[point.first][point.second] = true;
		for (auto idx = 0; idx < 4; ++idx)
		{
			auto nx = point.first + dx[idx];
			auto ny = point.second + dy[idx];
			if (0 <= nx && nx < N && 0 <= ny && ny < N && !visit[nx][ny] && (arr[nx][ny] <= shark_size))
			{
				tmp.first = nx; tmp.second = ny;
				node[nx][ny] = node[point.first][point.second] + 1;
				q.push(tmp);
				if ((arr[nx][ny] != 0) && (arr[nx][ny] < shark_size))
					eat_lists.push(make_tuple(node[nx][ny] - 1, nx, ny));
				visit[nx][ny] = true;
			}
		}
	}

	if (eat_lists.empty())
		return false;
	else
	{
		tuple<int, int, int> eat_item = eat_lists.top();
		int distance = get<0>(eat_item);
		int ex = get<1>(eat_item);
		int ey = get<2>(eat_item);

		while (!eat_lists.empty())
			eat_lists.pop();
		arr[now.first][now.second] = 0;
		arr[ex][ey] = 9;
		total_time += distance;
		++eat_count;
		if (eat_count == shark_size)
		{
			++shark_size;
			eat_count = 0;
		}
	}

	return true;
}

int main()
{
	shark_size = 2;
	total_time = 0;
	eat_count = 0;

	cin >> N;
	
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < N; ++iy)
			cin >> arr[ix][iy];
	}

	pair<int, int> point;
	while (true)
	{
		bool find = false;
		for (auto ix = 0; ix < N; ++ix)
		{
			for (auto iy = 0; iy < N; ++iy)
			{
				if (arr[ix][iy] == 9)
				{
					point.first = ix; point.second = iy;
					find = true;
					break;
				}
			}
			if (find)
				break;
		}
		if (!bfs(point))
			break;
	}
	cout << total_time << endl;
	return 0;
}
// *&)*@*

파이썬에 익숙해지고 싶었는데, 역시나 더 익숙한 언어가 간편하네요...