[백준]아기상어(3)

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

16236번: 아기 상어

매번 풀어도 재밌는 문제. bfs+vector(sort) or Priority Queue를 이용하는 문제이다. 

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
struct INFO {
    int r, c;
};
 
int N, R, C, ans = 0, SZ = 2, Eaten = 0;
int map[20][20],dis[20][20];
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
queue<INFO> q; //상어의 위치
vector<INFO> v; //물고기들의 위치
 
bool cmp(INFO a, INFO b) {
    if (a.r < b.r) return true;
    else if (a.r > b.r) return false;
    else {
        if (a.c < b.c) return true;
        else return false;
    }
}
 
void bfs() {
    while (!q.empty()) {
        int qlen = q.size();
        while (qlen--) {
            int r = q.front().r, c = q.front().c; q.pop();
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i], nc = c + dc[i];
                if (nr < 0 || nc < 0 || nr >= N || nc >= N || dis[nr][nc] != -1 || map[nr][nc]>SZ)continue;
                if (map[nr][nc] == 0 || map[nr][nc] == SZ) {
                    q.push({ nr,nc }); dis[nr][nc] = dis[r][c] + 1;
                }
                else if (map[nr][nc] < SZ) {
                    q.push({ nr,nc }); v.push_back({ nr,nc }); dis[nr][nc] = dis[r][c] + 1;
                }
            }
        }
        if (v.empty()) continue;
        sort(v.begin(), v.end(), cmp);
        ans += dis[v[0].r][v[0].c];
        Eaten++; map[v[0].r][v[0].c] = 0;
        if (Eaten == SZ) SZ++, Eaten = 0;
        while (!q.empty())q.pop(); q.push({ v[0].r,v[0].c }); //비워주기
        memset(dis, -1, sizeof(dis)); dis[v[0].r][v[0].c] = 0;
        v.clear();
    }
    printf("%d\n", ans);
}
 
void solve() {
    memset(dis, -1, sizeof(dis));
    q.push({ R,C }); dis[R][C] = 0;
    bfs();
}
 
int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        cin >> map[i][j];
        if (map[i][j] == 9) R = i, C = j, map[i][j] = 0;
    }
    solve();
    return 0;
}