<Baekjoon> #16236 BFS_아기상어 c++

#16236 아기상어
참고

아기상어
1. 처음의 크기는 2이고 상,하,좌,우로 1초에 한 칸씩 이동한다
2. 자신보다 크기가 큰 물고기가 있는 칸은 지나갈 수 없다
3. 자기보다 크기가 작은 물고기만 먹을 수 있다
4. 크기가 같은 물고기는 먹을 순 없지만 지나갈 수는 있다
5. 먹을 물고기의 우선 순위는 - 가장 가까운 물고기, 가장 위에 있는 물고기, 가장 왼쪽에 있는 물고기 순이다
6. 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다
7. 더 이상 먹을 물고기가 없다면 엄마 상어에게 도움을 요청한다

문제 풀이의 순서를 생각해보면
1. 현재 아기 상어의 위치에서 이동해, 먹을 수 있는 물고기들을 저장한다
2. 저장된 물고기들 중 가장 우선순위가 높은 물고기를 먹는다 (해당 위치로 이동)
3. 상어의 크기와 이때까지 먹은 물고기 수가 같다면 상어의 크기를 증가시킨다
4. 위 과정을 반복한다

아기상어가 먹을 물고기들은 아기상어로부터의 거리, 물고기의 위치를 저장해야하고, 우선 순위가 높은 순서대로 정렬해야 하기 때문에 priority queue를 사용할까 생각했다. 그렇게하면 comparison operator overloading 을 해야하는데 구현하는 게 헷갈려서 자신이 없었다.

그런데 vector<pair<pair<int, int>, int>> Eat 이렇게 선언하고, 처음부터 distance (아기 상어와 물고기 간 거리), y,x 를 차례대로 저장해서 sort를 하면 문제에서 주어진 우선순위대로 정렬이 된다.

1. hunting Fish

• 아기 상어의 위치 (y,x)가 주어졌을 때 이동할 수 있는 위치를 queue에 저장해 queue가 빌 때까지 반복하고, 이렇게 이동해서 먹을 수 있는 상어를 Eat에 저장한다.
• 아기 상어는 자신보다 작거나 같은 물고기는 지나갈 수 있지만 자신보다 작은 상어만 먹을 수 있다는 점을 유의한다

while (!q.empty()) {
	int cur_y = q.front().first;
	int cur_x = q.front().second;
	q.pop();

	for (int i = 0; i < 4; i++) {
		int nx_y = cur_y + dy[i];
		int nx_x = cur_x + dx[i];

		//범위 밖이면 이동하지 않는다
		if (nx_y < 0 || nx_x < 0 || nx_y >= N || nx_x >= N) continue;

		//한 번도 지나간 적 없고 자기보다 작거나 같은 칸은 지나간다
		if (distances[nx_y][nx_x] == 0 && sharkSize >= map[nx_y][nx_x]) {
			distances[nx_y][nx_x] = distances[cur_y][cur_x] + 1; 

            //물고기의 크기가 자기보다 작다면 먹을 물고기에 넣어준다
			if (map[nx_y][nx_x] > 0 && map[nx_y][nx_x] < sharkSize) 
					Eat.push_back(make_pair(make_pair(distances[nx_y][nx_x], nx_y), nx_x));

            //나머지 이동할 수 있는 위치는 queue에 넣어준다
			q.push(make_pair(nx_y, nx_x));
		}
	}
}

2. 상어가 물고기를 실제로 먹을 때

• 처음에는 9가 저장되어 있는 위치를 (baby_y, baby_x)라 두고 huntingFish를 호출
• huntingFish를 끝내고 오면 Eat에는 먹을 수 있는 물고기들이 저장되어 있다
• 만약 Eat이 비었다면 더 이상 먹을 수 있는 물고기가 없으므로 종료
• 비어있지 않다면 Eat을 문제에서 주어진 우선순위대로 정렬
• Eat[0]의 물고기를 먹고 그 위치로 상어를 이동한다
• 상어의 크기와 이때까지 먹은 물고기의 수가 같다면 상어의 크기 증가

	while (1) {
		huntingFish(baby_y, baby_x);
		if (Eat.empty()) break;
		else {
			sort(Eat.begin(), Eat.end());
			eatCnt++;
			ans += Eat[0].first.first;
			map[Eat[0].first.second][Eat[0].second] = 0;
			baby_y = Eat[0].first.second;
			baby_x = Eat[0].second;
			if (sharkSize == eatCnt) {
				sharkSize++;
				eatCnt = 0;
			}
		}
	}

전체코드

#include <iostream>
#include<string.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
const int MAX = 21;

int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };

int distances[MAX][MAX];
vector<vector<int>> map;
int sharkSize = 2;
int eatCnt = 0;
vector<pair<pair<int, int>, int>> Eat;

int ans = 0;
int N;
	
void huntingFish(int y, int x) {
	Eat.clear();
	memset(distances, 0, sizeof(distances));

	queue <pair <int, int>> q;
	q.push(make_pair(y, x));

	while (!q.empty()) {
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx_y = cur_y + dy[i];
			int nx_x = cur_x + dx[i];

			if (nx_y < 0 || nx_x < 0 || nx_y >= N || nx_x >= N) continue;
			//자기보다 큰 칸은 지나갈 수 없다
			if (distances[nx_y][nx_x] == 0 && sharkSize >= map[nx_y][nx_x]) {
				distances[nx_y][nx_x] = distances[cur_y][cur_x] + 1;
				if (map[nx_y][nx_x] > 0 && map[nx_y][nx_x] < sharkSize)
					Eat.push_back(make_pair(make_pair(distances[nx_y][nx_x], nx_y), nx_x));
				q.push(make_pair(nx_y, nx_x));
			}
		}
	}
}

int main() {
	int baby_y, baby_x;
	cin >> N;
	map = vector<vector<int>>(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				map[i][j] = 0;
				baby_y=i, baby_x=j;
			}
		}
	}
	while (1) {
		huntingFish(baby_y, baby_x);
		if (Eat.empty()) break;
		else {
			sort(Eat.begin(), Eat.end());
			eatCnt++;
			ans += Eat[0].first.first;
			map[Eat[0].first.second][Eat[0].second] = 0;
			baby_y = Eat[0].first.second;
			baby_x = Eat[0].second;
			if (sharkSize == eatCnt) {
				sharkSize++;
				eatCnt = 0;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

현재 위치의 상어가 먹을 수 있는 물고기들을 구조체로 만들어 저장하지 않고 pair을 이용하여 distance, y, x 순으로 저장하여 sort하는 아이디어를 생각하는게 이 문제를 쉽게 풀 수 있는 방법이다