[BOJ] #16236 _ 아기상어

[아기상어] https://www.acmicpc.net/problem/16236

16236번: 아기 상어

조건이 많은 문제이다.

물고기의 크기에 상관없이 무조건 가까이 있는 물고기를 먹기만 하면 된다.

따라서, BFS가 적합하다고 판단하였다.

 

1. BFS를 이용하여 가까운 거리에 먹을 수 있는 물고기가 있는지 확인한다.
2. 동일한 거리에 먹을 수 있는 물고기라면, 위쪽, 왼쪽의 물고기를 먹는다.
3. 상어의 크기 만큼의 물고기를 먹으면 상어의 크기는 1씩 증가한다.

 

위 조건을 생각하면서 구현하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
int dx[4] = { 0, -1, 1, 0 }, dy[4] = { -1, 0, 0, 1 };
int space[20][20] = { 0, };
int n, baby_size = 2, eaten = 0;
queue<pair<int, int> > q; //상어 시작 지점 (물고기 먹은 후 자리)
int bfs();
int main() {
	int result = 0;

	scanf("%d", &n);
	for (int i = 0; i < n; i++) { //Input data
		for (int j = 0; j < n; j++) {
			scanf("%d", &space[i][j]);
			if (space[i][j] == 9) {
				q.push(make_pair(i, j));
				space[i][j] = 0;
			}
		}
	}

	while (!q.empty()) {
		result += bfs();
		if (eaten == baby_size) { //상어 크기 증가
			baby_size++;
			eaten = 0;
		}
	}
	printf("%d", result);

	return 0;
}

int bfs() {
	queue<pair<int, int> > tmp_q = q; //상어가 먹을 물고기가 있는지 탐색하기 위한 큐
	pair<int, int> idx, tmp;
	int x, y;
	int check[20][20] = { 0, }, dist[20][20] = { 0, }, min_dist = 999999;
	q.pop();

	while (!tmp_q.empty()) {
		idx = tmp_q.front();
		tmp_q.pop();
		check[idx.first][idx.second] = 1;

		for (int i = 0; i < 4; i++) {
			y = idx.first + dy[i];
			x = idx.second + dx[i];

			if (x < 0 || y < 0 || x >= n || y >= n) continue;
			if (check[y][x] == 1 || space[y][x] > baby_size) continue;
			dist[y][x] = dist[idx.first][idx.second] + 1; //Set distance
			if (min_dist < dist[y][x]) continue;
			if (space[y][x] != 0 && space[y][x] < baby_size) { //Find Can Eat Fish
				if (min_dist == 999999) {
					min_dist = dist[y][x];
					tmp.first = y;
					tmp.second = x;
				}
				else if (y < tmp.first || (y == tmp.first && x < tmp.second)) { //같은 거리의 먹을 수 있는 물고기 중 위쪽, 왼쪽
					tmp.first = y;
					tmp.second = x;
				}
				continue;
			}
			check[y][x] = 1;
			tmp_q.push(make_pair(y, x));
		}
	}
	if (min_dist != 999999) { //Eat Fish
		q.push(make_pair(tmp.first, tmp.second));
		space[tmp.first][tmp.second] = 0;
		eaten++;
		return dist[tmp.first][tmp.second]; //먹은 물고기 거리 반환
	}

	return 0;
}