16236 아기 상어

 

16236번: 아기 상어

 

 

아기 상어가 물고기를 먹을 때마다 새롭게 BFS를 수행하면 된다.

조건만 빠뜨리지 않고 처리한다면 무난히 풀 수 있는 문제이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
using mypair = pair<int, int>;

int n;
int baby_shark = 2;
int space[20][20];
int visited[20][20];
int cnt;
int min_dist;

mypair target;
mypair curr_idx;
mypair steps[] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

void bfs(void) {

	queue<mypair> q;
	q.push(curr_idx);
	visited[curr_idx.second][curr_idx.first] = 0;

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

		for (int i = 0; i < 4; ++i) {
			int next_x = x + steps[i].first;
			int next_y = y + steps[i].second;
			
			if (next_x < 0 || next_x >= n || next_y < 0 || next_y  >= n) {
				continue;
			}

			if (visited[next_y][next_x] != -1 || space[next_y][next_x] > baby_shark) {
				continue;
			}
			
			visited[next_y][next_x] = visited[y][x] + 1;
			q.push({ next_x, next_y });

			if (space[next_y][next_x] != 0 && space[next_y][next_x] < baby_shark) {
				if (visited[next_y][next_x] < min_dist) {
					min_dist = visited[next_y][next_x];
					target = { next_x, next_y };
				}
				else if (visited[next_y][next_x] == min_dist) {
					if (next_y < target.second || (next_y == target.second && next_x < target.first)) {
						target = { next_x, next_y };
					}
				}
			}
			
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> space[i][j];
			if (space[i][j] == 9) {
				curr_idx = { j, i };
				space[i][j] = 0;
			}
		}
	}

	int time = 0;

	while (true) {
		memset(visited, -1, 20 * 20 * sizeof(int));
		min_dist = 987654321;

		bfs();
		if (min_dist != 987654321) {
			time += visited[target.second][target.first];
			++cnt;
			if (cnt == baby_shark) {
				baby_shark += 1;
				cnt = 0;
			}
			space[target.second][target.first] = 0;
			curr_idx = target;
		}
		else {
			break;
		}
	}

	cout << time;

	return 0;
}