백준 16236 c++ "아기 상어" -[PlusUltraCode]

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

16236번: 아기 상어

[필자 사고]

BFS탐색 문제이다. 문제를 이해하고 푸는 과정이 쉽지가 않았다.

 

문제는 쉽게 말해서 현재 위치에서 sero가 작은거부터 먹는다 만약 sero가 같은게 존재하면 garo가 작은걸 먹는다고 이해하면 쉽다. 

 

또한 배열 내에서 먼저 먹어야 하는게 존재하기 때문에 우선순위큐를 이용하여 먹을거에 우선순위를 부여했다.

 

중요한건 먹고나면 다시 BFS를 이용하여 먹을거에 우선순위를 구해야 된다는 점이다. 

 

구현에 있어서도 어려운 문제라고 생각한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> Node;

typedef struct Fish {
	int sero;
	int garo;
	int pathCount;

};
struct cmp {
	bool operator()(Fish a, Fish b) {
		if (a.pathCount == b.pathCount &&
			a.sero == b.sero) {
			return a.garo > b.garo;
		}
		else if (a.pathCount == b.pathCount) {
			return a.sero > b.sero;
		}
		return a.pathCount > b.pathCount;
	}
};


int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<vector<int>> Arr;
priority_queue<Fish, vector<Fish>, cmp> pq;
int N;
int fishSize = 2;
int eatCount = 0;
int ResultTime = 0;
bool gameOver = false;
int nowFishSero = 0;
int nowFishGaro = 0;


bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

void Input() {
	cin >> N;
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> Arr[i][k];
			if (Arr[i][k] == 9) {
				nowFishSero = i;
				nowFishGaro = k;
			}
		}
	}
}

void BFS(int sero, int garo) {
	vector<vector<int>> Arr2;
	vector<vector<int>> pathLoad;
	vector<vector<bool>> visited;
	priority_queue<Fish, vector<Fish>, cmp> pq2;
	visited.resize(N);
	pathLoad.resize(N);
	Arr2 = Arr;
	for (int i = 0; i < N; i++) {
		pathLoad[i].resize(N, 0);
		visited[i].resize(N, false);
		
	}
	queue<Node> myQueue;
	myQueue.push({ sero,garo });
	visited[sero][garo] = true;
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) &&
				visited[nextSero][nextGaro] == false&&
				Arr2[nextSero][nextGaro]<=fishSize) {
				
				visited[nextSero][nextGaro] = true;
				myQueue.push({ nextSero,nextGaro });
				pathLoad[nextSero][nextGaro] = pathLoad[nowSero][nowGaro] + 1;
				if (Arr2[nextSero][nextGaro] < fishSize&&Arr2[nextSero][nextGaro]>0) {
					pq2.push({ nextSero,nextGaro,pathLoad[nextSero][nextGaro] });
				}
			}
		}
	}
	pq = pq2;
}

void EatTime() {
	if (pq.empty()) {
		gameOver = true;
		return;
	}
	Fish fish = pq.top();
	int eatSero = fish.sero;
	int eatGaro = fish.garo;
	ResultTime += fish.pathCount;
	Arr[nowFishSero][nowFishGaro] = 0;
	Arr[eatSero][eatGaro] = 9;
	nowFishGaro = eatGaro;
	nowFishSero = eatSero;
	eatCount++;
	if (eatCount == fishSize) {
		fishSize++;
		eatCount = 0;
	}
}

int main(void) {

	Input();
	while (gameOver != true) {
	
		BFS(nowFishSero, nowFishGaro);
	
		EatTime();
	
	}
	cout << ResultTime;

}