[#16236] 아기상어

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Fish {
public:
	int row;  //물고기 있는 행
	int col;  //물고기 있는 열
	int size;  //물고기 사이즈

	//canEatFishVec에 있는것만 값 있음
	int fishVecindex;  //fishVec에서는 index가 몇번인지
	int distance;  //아기상어와의 거리

	Fish(int r, int c, int s) {
		row = r;
		col = c;
		size = s;
	}
};

int n;
vector<vector<int>> board;
vector<Fish> fishVec;  //전체 물고기
vector<Fish> canEatFishVec;  //먹을 수 있는 물고기
int sharkRow, sharkCol, sharkSize, sharkEatNum;  //아기상어 행, 열, 크기, 현재 먹은 물고기 갯수
int time = 0;  //시간. 답

//동서남북
int dRow[4] = { 0,0,1,-1 };
int dCol[4] = { 1,-1,0,0 };

void bfs() { 
	//아기상어로부터의 거리 구하기
	vector<vector<int>> distance(n, vector<int>(n, -1));
	queue<pair<int, int>> q;

	q.push({ sharkRow, sharkCol });
	distance[sharkRow][sharkCol] = 0;

	while (!q.empty()) {
		int hereRow = q.front().first;
		int hereCol = q.front().second;
		int hereD = distance[hereRow][hereCol];
		q.pop();

		for (int i = 0; i < 4; i++) {
			int thereRow = hereRow + dRow[i];
			int thereCol = hereCol + dCol[i];

			//범위안이고 내가 지나갈 수 있고 간 적 없다면
			if (0 <= thereRow && thereRow < n &&
				0 <= thereCol && thereCol < n &&
				board[thereRow][thereCol] <= sharkSize &&
				distance[thereRow][thereCol] == -1) {
				distance[thereRow][thereCol] = hereD + 1;
				q.push({ thereRow, thereCol });
			}
		}
	}

	//먹을 수 있는 물고기 체크
	//먹을 수 있다 <=> 크기가 상어 크기 이하 && 막혀있지 않음 (distance != -1)
	for (int i = 0; i < fishVec.size(); i++) {
		if (fishVec[i].size < sharkSize && distance[fishVec[i].row][fishVec[i].col] != -1) {
			//크기가 아기상어보다 작고 먹으러갈 수 있다면
			canEatFishVec.push_back(fishVec[i]);
			canEatFishVec.back().fishVecindex = i;  //방금 넣은 애의 index
			canEatFishVec.back().distance = distance[fishVec[i].row][fishVec[i].col];  //방금 넣은 애의 dist
		}
	}
}

//canEatFishVec의 몇번째 index를 먹으러 갈건지
void eat(int canEatFishVecIndex) {
	board[sharkRow][sharkCol] = 0; //상어가 이동했으니까 원래 상어 자리는 빈 자리로
	sharkRow = canEatFishVec[canEatFishVecIndex].row;  //상어는 물고기 자리로 이동
	sharkCol = canEatFishVec[canEatFishVecIndex].col;
	time += canEatFishVec[canEatFishVecIndex].distance;  //한칸 이동에 1초 걸리므로
	board[sharkRow][sharkCol] = 9;  //물고기 먹었으니까 그 자리에는 상어가

	sharkEatNum++; //물고기를 먹는다
	if (sharkSize == sharkEatNum) {  //현재 상어 크기만큼 물고기 먹었으면
		sharkSize++;  //상어 크기 + 1
		sharkEatNum = 0; 
	}

	//먹은 물고기 fishVec에서 제거
	//canEatFishVec은 while마다 새로 구하기 때문에 여기선 없애줄 필요 없음
	int fishVecindex = canEatFishVec[canEatFishVecIndex].fishVecindex;
	fishVec.erase(fishVec.begin() + fishVecindex);
}

int close() {
	//다음에 먹을 물고기의 canEatFishVec에서의 index return
	priority_queue<pair<pair<int, int>, pair<int, int>>> pq;  //-거리, -row, -col, canEatFishVec에서의 index
	for (int i = 0; i < canEatFishVec.size(); i++) {
		pq.push({ {-1 * canEatFishVec[i].distance, -1 * canEatFishVec[i].row}, { -1 * canEatFishVec[i].col, i} });
	}

	int ret = pq.top().second.second;  //index
	return ret;
}

int main() {

	scanf("%d", &n);
	board = vector<vector<int>>(n, vector<int>(n));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &board[i][j]);

			if (1 <= board[i][j] && board[i][j] <= 6) {
				Fish f(i, j, board[i][j]);
				fishVec.push_back(f);
			}

			else if (board[i][j] == 9) {
				sharkRow = i;
				sharkCol = j;
				sharkSize = 2;
				sharkEatNum = 0;
			}
		}
	}

	////////////////////////////

	
	while (true) {
		canEatFishVec.clear();  //매번 먹을 수 있는 물고기 새로 구하기
		bfs();  //먹을 수 있는 물고기 목록 구하기. row, col, distance, fistVecIndex

		if (canEatFishVec.empty()) {
			break;  //먹을 수 있는 물고기가 없다면
		}
		
		if (canEatFishVec.size() == 1) {
			eat(0);  //먹을 수 있는 물고기가 한마리라면 그 한마리 먹기. 하나니까 인덱스 무조건 0
		}
		else {
			int eatIndex = close();  //가장 가까운 물고기가 canEatFishVec에서 몇번 index인지
			eat(eatIndex);  //그 물고기 먹으러 간다
		}
	}

	cout << time;

	return 0;
}

거리 -> bfs

 

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

16236번: 아기 상어