백준 16236번 : 아기상어 - BFS C++

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

#include <bits/stdc++.h>
using namespace std;

int n, arr[21][21];
struct Shark {
	int x, y, size=2, cnt =0;
	void sizeUp() {
		if (cnt >= size) {
			cnt -= size;
			size++;
		}
	}
};

struct Node {
	int x, y , dist;

	bool operator<(const Node& b) const {
		if (dist == b.dist) {
			if (x == b.x) {
				return y > b.y;
			}
			return x > b.x;
		}
		else return dist > b.dist;
	}
};

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool ch[21][21];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	Shark sk;
	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) {
				arr[i][j] = 0;
				sk.x = i;
				sk.y = j;
			}
		}
	}

	priority_queue<Node> Q;
	Q.push({ sk.x, sk.y, 0 });
	ch[sk.x][sk.y] = 1;

	int ans = 0;

	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int d = Q.top().dist;
		Q.pop();

		if (arr[x][y]!=0 && arr[x][y] < sk.size) {
			arr[x][y] = 0;
			sk.cnt++;
			sk.sizeUp();

			memset(ch, 0, sizeof(ch));
			ans += d;

			while (!Q.empty()) {
				Q.pop();
			}
			Q.push({ x,y,0 });
			ch[x][y] = 1;
			continue;
		}


		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 || ch[nx][ny]) continue;
			if (arr[nx][ny] <= sk.size) {
				ch[nx][ny] = 1;
				Q.push({ nx,ny,d + 1 });
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

백준 16236번 아기상어