C++:: boj 16236 < 아기 상어 >

주어지는 조건이 좀 많아서 문제를 자세히 읽고 풀어야 하는 문제이다.
주의해야 할 점으로 이동 가능한 곳이 여러 곳 일때는 우선순위가 위쪽, 왼쪽 에 있는 순이며 물고기를 자신의 크기수 만큼 먹었을때 상어의 크기가 증가한다는 점이다.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int n, baby_size = 2, eat_cnt, answer;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

pair<int, int> baby;

int main() {
	cin >> n;
	vector<vector<int>> board(n, vector<int>(n));
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			cin >> board[i][j];
			if (board[i][j] == 9) {
				board[i][j] = 0;
				baby = {i, j};
			}
		}
	}

	while (1) {
		vector<vector<int>> vis(n, vector<int>(n, -1));
		deque<pair<int, int>> dq = {baby};
		pair<int, int> cur, target = {INT32_MAX, INT32_MAX};
		int dist = INT32_MAX;
		vis[baby.first][baby.second] = 0;
		while (!dq.empty()) {
			cur = dq.back();
			dq.pop_back();
			for (int dir=0; dir<4; dir++) {
				int nx = cur.first + dx[dir], ny = cur.second + dy[dir];
				if (nx<0 || ny<0 || nx>=n || ny>=n) continue;
				if (vis[nx][ny]>=0 || board[nx][ny] > baby_size) continue;// 이미 방문 했거나, 물고기 크기가 상어보다 크다면
				if (vis[cur.first][cur.second] + 1 > dist) continue;// 이미 찾은 곳보다 멀다면
				if (board[nx][ny] && board[nx][ny] != baby_size &&
					(target.first > nx || (target.first == nx && target.second > ny))) {// 먹을 수 있다면
						dist = vis[cur.first][cur.second] + 1;
						target = {nx, ny};
				}
				vis[nx][ny] = vis[cur.first][cur.second] + 1;
				dq.push_front({nx, ny});
			}
		}
		if (dist == INT32_MAX) break;// 먹은 적 없다면
		answer += dist;
		baby = target;
		board[baby.first][baby.second] = 0;
		if (++eat_cnt == baby_size) {// 사이즈 만큼 먹었다면
			baby_size++;
			eat_cnt = 0;
		}
	}
	cout << answer << "\n";
}