백준/16236번/아기 상어/골드3

Problem Link: https://www.acmicpc.net/problem/16236

문제 설명

Site: Baekjoon
Number: 16236
Category: BFS
Rank: Gold 3

BFS를 통해 상어가 먹을 수 있는 먹이의 위치를 지속적으로 파악하여 더 이상 먹이를 탐색할 수 없을때까지 진행하는 문제.

주의점
기본적으로 문제를 BFS로 해결하지만 조건을 통해 BFS 순서를 위 좌 우 상으로 진행하여도 틀리는 상황이 발생한다.

위 좌 우 상으로 탐색을 진행하는 BFS는 아래와 같은 탐색 순서를 갖는다.

9번과 10번을 보면 거리는 2로 같지만, 탐색 순서는 9번이 먼저 오기 때문에 틀리게 된다.

이를 해결하기 위해 걸리는 먹이의 좌표와 거리를 모두 벡터에 넣은 후 정렬하여 가장 적은 거리의 위+왼쪽에 있는 먹이를 먹는 방식으로 풀이하였다.

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
#include <memory>

#define PII pair<int, int>
#define TIII tuple<int, int, int>

using namespace std;

int N, arr[20][20], SharkSize = 2, EatCount, Time;
bool visited[20][20];

int dirx[4] = { -1, 0, 0, 1 };
int diry[4] = { 0, -1, 1, 0 };

PII BFS(PII Shark)
{
	PII start = Shark;

	queue<TIII> q;
	vector<TIII> v;

	q.push(TIII(start.first, start.second, 0));

	visited[Shark.first][Shark.second] = true;

	while(!q.empty())
	{
		TIII tmp = q.front();
		q.pop();

		for(int i = 0; i < 4; i++)
		{
			int newx = get<0>(tmp) + dirx[i];
			int newy = get<1>(tmp) + diry[i];

			if (newx < 0 || newx > N - 1 || newy < 0 || newy > N - 1 || visited[newx][newy] == true || arr[newx][newy] > SharkSize)
				continue;

			if (arr[newx][newy] != 0 && arr[newx][newy] < SharkSize)
				v.emplace_back(newx, newy, get<2>(tmp)+1);
			else
			{
				q.push(TIII(newx, newy, get<2>(tmp)+1));
				visited[newx][newy] = true;
			}
		}
	}

	if(!v.empty())
	{
		sort(v.begin(), v.end(), [](TIII a, TIII b)
		{
			if(get<2>(a) == get<2>(b))
			{
				if (get<0>(a) == get<0>(b))
					return get<1>(a) < get<1>(b);
				else
					return get<0>(a) < get<0>(b);
			}
			return get<2>(a) < get<2>(b);
		});

		Time += get<2>(v[0]);
		return PII(get<0>(v[0]), get<1>(v[0]));
	}

	return start;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	PII Shark;

	cin >> N;

	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			cin >> arr[i][j];
			if(arr[i][j] == 9)
			{
				Shark.first = i;
				Shark.second = j;
			}
		}
	}

	PII next = BFS(Shark);

	while(next != Shark)
	{
		memset(visited, false, sizeof(bool) * 20 * 20);

		if(++EatCount == SharkSize)
		{
			EatCount = 0;
			SharkSize++;
		}

		arr[Shark.first][Shark.second] = 0;
		arr[next.first][next.second] = 9;

		Shark = next;
		next = BFS(Shark);
	}

	cout << Time;

	return 0;
}