[BOJ] 16236 아기 상어 / C++

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

16236번: 아기 상어

 

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int MAP[30][30]; // 0: 빈칸, 1 ~ 6: 물고기의 크기, 9: 아기 상어의 위치
int dist[30][30];

int answer = 0;

int dr[] = { -1,0,1,0 };
int dc[] = { 0,-1,0,1 };

struct SHARK {
	int r, c, size, eatenFish;
};

SHARK shark; // 아기상어의 정보를 저장하는 구조체

queue <pair<int, int> > q;
vector <pair<int, int> > fish;

bool isEatableFishExist = true;

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &MAP[i][j]);
			if (MAP[i][j] == 9)
			{
				shark.r = i;
				shark.c = j;
				shark.size = 2;
				shark.eatenFish = 0;

				q.push(make_pair(shark.r, shark.c));
				MAP[i][j] = 0;
			}
		}
	}
}


void clear_dist()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			dist[i][j] = -1;
		}
	}
}

void bfs(int r, int c)
{
	dist[r][c] += 1;

	while (!q.empty())
	{
		int cur_r = q.front().first;
		int cur_c = q.front().second;

		q.pop();

		for (int k = 0; k < 4; k++)
		{
			int nr = cur_r + dr[k];
			int nc = cur_c + dc[k];

			if (nr < 0 || nr >= N || nc < 0 || nc >= N || dist[nr][nc] != -1) continue;
			if (MAP[nr][nc] > shark.size) continue;
			else if (MAP[nr][nc] < shark.size && MAP[nr][nc] != 0)
			{
				fish.push_back(make_pair(nr, nc));
			}
			dist[nr][nc] = dist[cur_r][cur_c] + 1;
			q.push(make_pair(nr, nc));
		}
	}
}

bool cmp(pair<int, int> p1, pair<int, int> p2)
{
	if (dist[p1.first][p1.second] < dist[p2.first][p2.second])
	{
		return true;
	}
	else if (dist[p1.first][p1.second] == dist[p2.first][p2.second])
	{
		if (p1.first < p2.first) return true;
		else if (p1.first == p2.first)
		{
			if (p1.second < p2.second) return true;
		}
	}
	return false;
}

void solve()
{	
	while (isEatableFishExist)
	{
		clear_dist();

		q.push(make_pair(shark.r, shark.c));
		bfs(shark.r, shark.c);

		int numFish = fish.size();

		if (numFish == 0)
		{
			isEatableFishExist = false;
		}
		else
		{
			sort(fish.begin(), fish.end(), cmp);

			shark.r = fish[0].first;
			shark.c = fish[0].second;
			MAP[shark.r][shark.c] = 0;
			shark.eatenFish++;
			answer += dist[shark.r][shark.c];
			fish.clear();
		}
		if (shark.eatenFish == shark.size)
		{
			shark.size += 1;
			shark.eatenFish = 0;
		}
	}

}

int main(void)
{
	input();
	solve();
	printf("%d\n", answer);

	return 0;
}