BaekJoon 16236번: 아기상어(C++)

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

16236번: 아기 상어

풀이법

1) BFS와 구현이 합쳐진 문제였으며 고려해야할 예외처리가 많아서 힘들었던 문제이다.

2) 현재 아기 상어의 크기보다 작은 값이 있는 경우 탐색을 계속 진행하며, bfs를 반복하며 탐색을 진행했다. 작은 값이 존재하나 갈수 없는 곳이 존재하면 탐색을 중지하였다.

3) 현재 아기 상어의 크기만큼 아기 상어가 물고기를 먹으면 사이즈가 증가하는 것을 꼭 고려해 주어야 하며 아기 상어가 먹은 곳은 0으로 값을 다시 바꾸어 주었다.

4) 아기 상어의 값이 9로 되어 있으니 비교 시에 아기상어의 값보다 작은 값들만 넣어준다와 같은 룰을 적용하게 되면 들어갈 수 있는 값이 1+2+3+...+8까지 한정적일 수 있기에 물고기의 최대 크기인 6이상으로 아기상어의 크기가 커지는 경우 크기의 제한을 구현했다.

5) BFS내에서는 같은 거리에 있을 경우, 위쪽, 혹은 왼쪽의 값을 제일 먼저 방문해야 하기에 sort 내의 compare 문을 재정의 하여 값을 맞출 수 있도록, 가능한 값들을 vector에 넣어서 sort 시켰다.

 

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>
#include <math.h>
using namespace std;

int n;
int arr[21][21];
bool visited[21][21];
int startX, startY;
int nowSize = 2;
int nowCnt = 0;
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int ans = 0;
bool compare(pair<int, int> a, pair<int, int> b)
{
	if (a.first < b.first)
		return true;
	else if (a.first == b.first)
	{
		if (a.second < b.second)
			return true;
		else
			return false;
	}
	else
		return false;
}
int checkSmall()
{
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j]!=0 && arr[i][j] < nowSize)
				cnt++;
		}
	}
	return cnt;
}
int bfs(int a, int b)
{
	queue<pair<int, pair<int, int>>> q;
	int minSec=0;
	visited[a][b] = true;
	q.push({ a,{b,0} });
	vector<pair<int, int>> vec;
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second.first;
		int cnt = q.front().second.second;
		q.pop();
		if (arr[nowX][nowY] != 0 && arr[nowX][nowY]<nowSize)
		{
			minSec = cnt;
			vec.push_back({ nowX,nowY });
			while (!q.empty())
			{
				nowX = q.front().first;
				nowY = q.front().second.first;
				int Ccnt = q.front().second.second;
				q.pop();
				if (Ccnt != cnt)
					break;
				if (arr[nowX][nowY] != 0 && arr[nowX][nowY] < nowSize)
				{
					vec.push_back({ nowX,nowY });
				}
			}
			break;
		}
		else {
			for (int i = 0; i < 4; i++)
			{
				int nextX = nowX + vx[i];
				int nextY = nowY + vy[i];
				if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= n)
					continue;
				if (arr[nextX][nextY] <= nowSize && !visited[nextX][nextY])
				{
					visited[nextX][nextY] = true;
					q.push({ nextX,{nextY,cnt + 1} });
				}
			}
		}
	}
	if (vec.size() >= 1)
	{
		sort(vec.begin(), vec.end(), compare);
		nowCnt++;
		startX = vec[0].first;
		startY = vec[0].second;
		arr[a][b] = 0;
		arr[startX][startY] = 9;
	}
	return minSec;
}
void clearVisited()
{
	for(int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			visited[i][j] = false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	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)
			{
				startX = i;
				startY = j;
			}
		}
	}
	while (checkSmall())
	{
		clearVisited();
		int t=bfs(startX, startY);
		if (t == 0)
			break;
		ans += t;
		if (nowCnt == nowSize)
		{
			if (nowSize >= 7)
				continue;
			nowSize++;
			nowCnt = 0;
		}
	}
	cout << ans;
}