백준 16236 아기 상어

https://acmicpc.net/problem/16236 

16236번: 아기 상어

 

- 1시간 10분이 걸린 문제.. 문제 조건을 꼼꼼하게 잘 읽고 풀었으면 10분은 단축시킬 수 있었을듯함

 

- BFS + 구현 문제이다. 시간복잡도는 의미없을 듯. BFS는 O(N^2)

 

- BFS를 진행하는 동안 해야 하는 것들을 살펴보면

 

  1) 물고기를 발견했을 때

 

    (1) 물고기가 상어보다 크다면 탐색 중단 

    (2) 크기가 같다면 queue에만 push. 지나갈 수는 있기 때문이다.

    (3) 작다면 먹을 수 있는 대상이다. 따로 vector에 해당 좌표를 push하고, 거리도 미리 저장을 해 둔다.

 

  2) 나보다 큰 물고기를 제외한 모든 구역들과 현재 상어의 구역과의 거리를 dist 배열에 저장한다.

 

- BFS를 마쳤을 때, 먹을 수 있는 물고기 후보군을 스캔하는데 만약 후보군이 없다면 엄마 상어를 호출해야 하므로 false를 return한다. 후보군이 있다면 최소 거리를 갖는 물고기를 한 번 더 필터링 해 준다. 그 후, 해당 벡터에 sort를 진행 할 건데 compare 커스텀 함수를 추가로 만들어 준다. 왜냐하면 x좌표, y좌표가 가장 작은 물고기를 먹어야 하기 때문이다. sort를 완료했다면 가장 맨 앞의 좌표를 선택해서, 해당 좌표의 물고기를 먹고 shark를 그 좌표로 이동시킨다. 추가로, shark의 크기를 늘릴 지를 체크 해 주고 true를 return한다.(물론 answer에도 이동거리를 추가 해 주어야 함.) 

 

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

int dx[] = { 0,0,1,-1 };
int dy[] = { -1, 1,0,0 };
int arr[20][20];
int dist[20][20];
bool visited[20][20];
int n, answer;
int shark_x, shark_y,ate_fish, shark_size = 2;

bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first) return a.second < b.second;
	return a.first < b.first;
}

bool BFS(int start_x, int start_y) {
	int min_distance = 500;
	vector<pair<int, int>> possible_fish;
	queue<pair<pair<int, int>, int>> next_area;
	visited[shark_x][shark_y] = true;
	next_area.push({ {shark_x, shark_y}, 0 });
	while (!next_area.empty()) {
		int now_distance = next_area.front().second;
		int x = next_area.front().first.first;
		int y = next_area.front().first.second;
		next_area.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue;
			visited[nx][ny] = true;
			if (arr[nx][ny] != 0 && arr[nx][ny] != 9) { // 물고기인 경우
				if (arr[nx][ny] > shark_size) continue; // 물고기가 상어보다 큰 경우 pass
				else if (arr[nx][ny] == shark_size) { // 물고기가 상어와 같은 경우 지나갈 수 있게만 표시
					dist[nx][ny] = now_distance + 1;
					next_area.push({ { nx,ny }, now_distance + 1 });
					continue;
				}
				possible_fish.push_back({ nx,ny });
				min_distance = min(min_distance, now_distance + 1);
			}
			dist[nx][ny] = now_distance + 1;
			next_area.push({ {nx,ny}, now_distance + 1 });
		}
	}
	if (possible_fish.size() == 0) return false;
	vector<pair<int, int>> close_fish;
	for (int i = 0; i < possible_fish.size(); i++) {
		int x = possible_fish[i].first;
		int y = possible_fish[i].second;
		if (dist[x][y] == min_distance) close_fish.push_back({ x,y });
	}
	sort(close_fish.begin(), close_fish.end(), compare);
	arr[close_fish.front().first][close_fish.front().second] = 9;
	arr[shark_x][shark_y] = 0;
	shark_x = close_fish.front().first;
	shark_y = close_fish.front().second;
	answer += min_distance;
	ate_fish++;
	if (ate_fish == shark_size) {
		shark_size++;
		ate_fish = 0;
	}
	memset(dist, 0, sizeof(dist));
	memset(visited, false, sizeof(visited));
	
	return true;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				shark_x = i;
				shark_y = j;
			}
		}
	}
	while (BFS(shark_x, shark_y));
	cout << answer;
	return 0;
}