백준 16236번 아기 상어 C++

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

 

매 턴마다 먹을 수 있고 갈 수 있는 위치에 있는 물고기를 탐색하여서 그 중 가장 거리가 작은 물고기를 찾아서 먹고 먹을만큼 먹으면 크기가 커지는 것을 구현해서 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

struct Fish {
	int size;
	int row;
	int col;
	bool operator==(const Fish& fish) {
		if (size == fish.size && row == fish.row && col == fish.col) return true;
		return false;
	}
};

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };
int n, sharkSize, sharkRow, sharkCol;
int cnt = 0;
vector<vector<int>> board(20, vector<int>(20, 0));
vector<Fish> fishes;

bool compare(const pair<int, Fish>& lhs, const pair<int, Fish>& rhs) {
	if (lhs.first == rhs.first) {
		if (lhs.second.row == rhs.second.row) {
			return lhs.second.col < rhs.second.col;
		}
		return lhs.second.row < rhs.second.row;
	}
	return lhs.first < rhs.first;
}

bool SmallerThanShark(Fish fish) {
	if (fish.size < sharkSize) return true;
	return false;
}

int GetDist(Fish fish) {
	int ret = -1;
	queue<pair<pair<int, int>, int>> q;
	vector<vector<bool>> found(n, vector<bool>(n, false));
	found[sharkRow][sharkCol] = true;
	q.push({ {sharkRow,sharkCol},0 });
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		if (curr.first.first == fish.row && curr.first.second == fish.col) {
			ret = curr.second;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nextRow = curr.first.first + dRow[i];
			int nextCol = curr.first.second + dCol[i];
			if (nextRow >= n || nextRow < 0) continue;
			if (nextCol >= n || nextCol < 0) continue;
			if (found[nextRow][nextCol]) continue;
			if (board[nextRow][nextCol] > sharkSize) continue;
			found[nextRow][nextCol] = true;
			q.push({ {nextRow,nextCol},curr.second + 1 });
		}
	}
	return ret;
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int input;
			cin >> input;
			if (input == 0) continue;
			if (input == 9) {
				sharkSize = 2;
				sharkRow = i;
				sharkCol = j;
				board[i][j] = 9;
				continue;
			}
			fishes.push_back({ input,i,j });
			board[i][j] = input;
		}
	}
	int growCnt = 0;
	while (true) {
		vector<pair<int, Fish>> possibleFishes;
		for (auto fish : fishes) {
			int dist = GetDist(fish);
			if (SmallerThanShark(fish) && (dist != -1))
				possibleFishes.push_back({ dist,fish });
		}
		if (possibleFishes.size() == 0) break;
		sort(possibleFishes.begin(), possibleFishes.end(), compare);

		cnt += possibleFishes[0].first;
		growCnt++;
		if (growCnt == sharkSize) {
			sharkSize++;
			growCnt = 0;
		}
		board[sharkRow][sharkCol] = 0;
		sharkRow = possibleFishes[0].second.row;
		sharkCol = possibleFishes[0].second.col;
		board[sharkRow][sharkCol] = 9;

		auto it = find(fishes.begin(), fishes.end(), possibleFishes[0].second);
		fishes.erase(it);
	}
	cout << cnt;
};