[BOJ] 백준 16236번 : 아기상어 C++ : 아주정은

아기상어... 이문제는 삼성 코딩테스트를 준비할때, 기출문제로 풀기를 시도한적있다.

그 때는 풀지 못하였다. 하지만 우선순위 큐에 대해 공부하고, 비교적 쉽게? 풀수있었다.

우선 배열을 다 돌면서 나보다 작은것들을 우선순위 큐에 집어넣고 우선순위에 따라 먹이를 준다.

그리고 vis랑 우선순위 큐를 초기화 해준다. 그러면 끄읕!

초기화에만 항상 신경을 써주자!

#include<iostream>
#include <cstdio>
#include<cstring>
#include <queue>
using namespace std;

struct Que {
	int x;
	int y;
	int time;
};

struct cmp {
	bool operator()(Que t, Que u) {
		if (t.time == u.time) {
			if (t.x == u.x) {
				return t.y > u.y;
			}
			else {
				return t.x > u.x;//value에 대해 내림차순임
			}
		}
		else {
			return t.time > u.time;
		}
	}
};

int board[21][21];
bool vis[21][21];

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

using namespace std;

int main() {
	int N;
	queue<Que> Q;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 9) {
				Q.push({ i,j,0 });
				board[i][j] = 0;
				vis[i][j] = true;
			}
		}
	}
	int vol = 2;
	int brun = 0;
	int time=0;
	while (1) {
		//int size = Q.size();
		priority_queue<Que, vector<Que>, cmp> PQ;
		while (!Q.empty()) {
			auto cur = Q.front();
			Q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if (board[nx][ny] > vol or nx<0 or nx>N - 1 or ny<0 or ny>N - 1)continue;
				if (board[nx][ny] <= vol and vis[nx][ny] == false) {
					Q.push({ nx,ny,cur.time+1 });
					vis[nx][ny] = true;
					if (board[nx][ny] < vol and board[nx][ny]!=0) {
						PQ.push({ nx,ny,cur.time + 1 });
					}
				}
			}
		}
		
		memset(vis, false, sizeof(vis));
		if (!PQ.empty()) {
			auto cur = PQ.top();
			PQ.pop();
			board[cur.x][cur.y] = 0;
			brun++;//먹으면 증가
			time = cur.time;
			Q.push({ cur.x,cur.y,cur.time });
			vis[cur.x][cur.y] = true;
		}
		else {
			cout << time << endl;
			break;
		}
		
		if (brun == vol) {
			vol++;
			brun = 0;
		}
	}
}