BOJ 16236: 아기 상어

#BOJ 16236: 아기 상어

16236번: 아기 상어

#풀이

보자마자 bfs를 사용해서 풀 수 있다고 생각했다.

 

일단 상어가 가장 가까운 물고기를 먹으면 그 자리에서 가장 가까운 물고기를 찾아야한다.

 

거리가 가까운 물고기가 여러 개 있을 때 우선순위는 가장 높고 왼쪽에 있는 물고기를 먹으러 가야 한다.

 

그래서 나는 맨 처음 상어의 자리에서 부터 bfs를 돌린다.

 

큐에 넣지 않는 조건은 배열을 넘어갔을 때 자기의 몸집보다 클 때 이다.

 

맨 처음에는 그냥 dx, dy로 우선순위를 해결할 수 있다고 생각이 들어 간단하게 구현했는데 

x가 0 일 때 같은 x에 있는 물고기가 아닌 아래에 있는 물고기를 먹으러 갔다.

 

그래서 먹을 수 있는 물고기 중에서 가장 우선순위가 높은 물고기를 먹게 하였다.

 

자기 몸집보다 작은 물고기를 만나면 우선순위 큐(최소힙)에 <물고기와의 거리, x , y> 넣었다.

 

그러면 가장 가까운 거리의 물고기를 꺼내올 수 있다.(정렬 : 거리 -> x-> y)

 

물고기를 먹으면 baby_prey를 증가시키고 조건에 맞게 baby_num(상어크기) 를 증가 시키면 된다.

또한 물고기를 먹은 자리에서 다시 bfs를 시작해야 하기 때문에 vis배열 초기화와 물고기 먹은 자리의 원소를 0으로 바꿔줘야 한다.

 

n의 크기가 20으로 작아 충분히 2초 안에 해결할 수 있을 것 같았다.

 

간단하게 구현할 수 있다.

 

 

 

#코드

#include<iostream>
#include<queue>
#include<tuple>
using namespace std;
int n;
int arr[21][21];
int baby_prey = 0;
int baby_num = 2;
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0,-1, 1, 0 };
int fish = 0;
int ans;
void bfs(int shark_x, int shark_y) {
	int vis[21][21] = {0,};
	queue<pair<int, int>> q;
	priority_queue<tuple<int,int, int>, vector<tuple<int,int, int>>, greater<tuple<int,int,int>>>pq;
	q.push({ shark_x, shark_y });
	vis[shark_x][shark_y] = 1; // 상어 자리 1로 두는 이유는 어차피 bfs로 이동할 때 물고기가 없는 자리인데 다시 되돌아가지 않게 하기 위해서
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		
		for (int i = 0; i < 4; i++) {
			int x = cur.first + dx[i];
			int y = cur.second + dy[i];
			
			if (x < 1 || y < 1 || x > n || y > n || vis[x][y] != 0 || arr[x][y] > baby_num)
				continue;
			
			if (arr[x][y] != 0 && arr[x][y] < baby_num) // 자기 몸집보다 작은 물고기를 만났을 때
			{
				pq.push({ vis[cur.first][cur.second], x,y });
				continue;
			}
			vis[x][y] = vis[cur.first][cur.second] + 1;
			q.push({ x,y });
		}
	}
	if (!pq.empty()) // 먹을 수 있는 물고기가 있는지 확인 
	{
		int p_age, p_x, p_y;
		tie(p_age, p_x, p_y) = pq.top(); pq.pop();
		ans += p_age; // 상어의 자리에서 부터 거리
		arr[p_x][p_y] = 0;
		fish--;
		if (fish <= 0) // 물고기를 다 잡아먹으면 리턴
			return;
		baby_prey++;
		if (baby_num == baby_prey) { // 상어크기 변화
			baby_prey = 0;
			baby_num++;
		}
		bfs(p_x, p_y); // 다시 잡아먹은 물고기 자리에서 부터 bfs 시작
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int shark_x = 0;
	int shark_y = 0;

	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] != 9 && arr[i][j] != 0) // 물고기를 다 잡아 먹는지 확인하기 위한 카운트
				fish++;
			if (arr[i][j] == 9) // 상어는 편의상 0으로 대입
			{
				shark_x = i;
				shark_y = j;
				arr[i][j] = 0;
			}
			

		}
	}
	if(fish !=0) // 입력 시 배열에 물고기가 한마리도 없으면 무조건 0
		bfs(shark_x, shark_y);
	cout << ans << '\n';
	return 0;
}