[BOJ 16236] 아기 상어

백준 :: BOJ :: 16236 :: 아기 상어

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

#include <bits/stdc++.h>

using namespace std;

int N, t, tt, fs, ss, si, sj, ni, nj,

arr[21][21], v[21][21], di[] = {-1,0,0,1}, dj[] = {0,-1,1,0};

queue<pair<int, int>> q; priority_queue<int,vector<int>,greater<int>> pq;

void clear() { 

queue<pair<int, int>> e; priority_queue<int, vector<int>, greater<int>>ee; swap(pq, ee); swap(q, e);

memset(v, 0, sizeof(v)); q.push(make_pair(ni, nj)); 

}

void bfs() {

while (!q.empty()) {

int s = q.size(); tt++;

while (s--) {

auto tmp = q.front(); q.pop();

for (int d = 0; d < 4; d++) {

ni = tmp.first + di[d]; nj = tmp.second + dj[d];

if (ni > 0 && ni <= N && nj > 0 && nj <= N && arr[ni][nj] <= ss &&!v[ni][nj]) {

if (arr[ni][nj] < ss && arr[ni][nj] >0) pq.push(ni*100+nj);

else v[ni][nj] = 1, q.push(make_pair(ni, nj));

}

}

}

if (!pq.empty()) {

ni = pq.top() / 100; nj = pq.top() % 100;

fs++; arr[ni][nj] = 0; clear(); t += tt; tt = 0;

if (ss == fs) ss++, fs = 0;

}

}

}

int main() {

std::ios::sync_with_stdio(false); cin.tie(0);

cin >> N; t = 0; ss = 2; fs = 0;

for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {

cin >> arr[i][j]; if (arr[i][j] == 9) arr[i][j]=0, si = i, sj = j, q.push(make_pair(i,j));

}

bfs();

cout << t;

return 0;

}