[백준OJ] 16236번 아기상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

---

-풀이-

간단한 bfs문제이다.

1. BFS를 이용하여 배열을 돌며 먹을 수 있는 먹이와 그 먹이까지의 거리를 구해서 vector에 넣어준다.

2. 모든 먹이들을 우선순위에 맞게 정렬을 해준다.

-1순위:먹을 수 있는 먹이중 가장 짧은 거리

-2순위:짧은거리가 여러개면 가장 위에있는 먹이

-3순위:2순위도 많다면 가장 왼쪽에 있는 먹이

3. 2번의 결과가 0개이면, 어미 상어를 호출한다.

4. 3번에서 안걸렸다면, 아기상어가 먹을 수 있는것이 1개이상 있다고하는데, 이미 우선순위에따라 정렬이 되어있으므로, 2번의 결과의 맨 앞부분의 먹이를 먹으러 가면된다.

5. 먹이를 먹고, 해당 배열의 값을 비어있다는 의미로 0으로 초기화 해준뒤, 아기상어의 위치를 업데이트 하고, 먹이의 개수와 사이즈가 같다면, 사이즈를 1 올려준다.

 

-시간 복잡도-

1. BFS의 시간은 모든 배열을 도는 것이므로 O(N*N)

2. algorithm헤더의 sort함수는 퀵 소트이므로 O(NlogN)

3,4,5 는 상수시간 안에 해결가능하므로 O(1)

 

따라서 총 시간복잡도는 O(N*N)이 된다.

 

-코드-

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

typedef pair<int, int> pii;

int n, m;
int arr[20][20], mv[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
pii b_shark;
int sz = 2;

void input() {
	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) {
				b_shark = { i,j };
				arr[i][j] = 0;
			}
		}
	}
}

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

bool isIn(int x, int y) {
	return x >= 0 && x < n&&y >= 0 && y < n;
}

vector<pair<pair<int,int>,int>> check_food() {
	queue<pair<pair<int, int>, int>> q;
	vector<pair<pair<int, int>, int>> result;
	bool visited[20][20] = { 0 };

	q.push({ { b_shark.first,b_shark.second }, 0 });
	visited[b_shark.first][b_shark.second] = true;

	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int dst = q.front().second;

		q.pop();

		if (arr[x][y] < sz&&arr[x][y]!=0) {
			result.push_back({ {x,y},dst });
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + mv[i][0];
			int ny = y + mv[i][1];

			if (isIn(nx, ny) && !visited[nx][ny]&& arr[nx][ny] <= sz) {
				q.push({ {nx,ny},dst + 1 });
				visited[nx][ny] = true;
			}
		}
	}
	sort(result.begin(), result.end(), compare);
	return result;
}

void solve() {
	int time = 0;
	int cnt = 0;
	while (true) {
		vector<pair<pair<int,int>,int>> food = check_food();
		if (food.size() == 0) {
			break;
		}
		else {
			int nx = food[0].first.first;
			int ny = food[0].first.second;
			int t = food[0].second;
			time += t;
			b_shark.first = nx;
			b_shark.second = ny;
			arr[nx][ny] = 0;
			cnt++;
			if (cnt == sz) {
				sz++;
				cnt = 0;
			}
		}
	}
	cout << time << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	input();
	solve();
}