백준(BOJ) 16236 - 아기 상어

아기상어 문제를 풀었다.

하반기에 한번 풀어본 문제여서 같은 방법으로 접근했다.

bfs로 먹을수 있는 물고기를 탐색한 다음 소팅하여 가장 우선순위가 높은 물고기를 선택하였다.

조건들만 잘 넣어준다면, 어렵지 않게 풀수 있는 문제이다.

풀고 나서 생각이 든 것인데, 가장 우선순위가 높은 하나만 선택하면 되기때문에

덱을 사용하여  비어있거나 0번 인덱스 물고기보다 우선순위가 낮은 물고기는 뒤에 푸쉬하고 우선순위가 높은 물고기는 앞에 푸쉬를 한면, 소팅을 안해도 될 것 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct _pair{
    int y;
    int x;
    int cnt;
 
};
 
bool cmp(_pair a, _pair b){
    if(a.cnt < b.cnt) return true;
    if(a.cnt == b.cnt){
        if(a.y < b.y) return true;
        if(a.y == b.y){
            if(a.x < b.x) return true;
        }
    }
 
    return false;
}
int N;
int shark_y, shark_x, shark_size, eat_cnt, total_second;
int map[21][21];
 
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool bfs(vector<_pair>& fishes){
    queue<_pair> q;
    bool visited[21][21];
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            visited[i][j] = false;
        }
    }
    visited[shark_y][shark_x] = true;
    q.push({shark_y, shark_x, 0});
    while(!q.empty()){
        _pair p = q.front();
        q.pop();
        for(int i = 0 ; i < 4; i++){
            int ny = p.y + dy[i];
            int nx = p.x + dx[i];
            if(ny < 0 || ny >= N || nx < 0 || nx >= N
                || visited[ny][nx] || map[ny][nx] > shark_size){
                continue;
            }
            visited[ny][nx] = true;
            q.push({ny,nx,p.cnt + 1});
            if(map[ny][nx] > 0 && map[ny][nx] < shark_size){
                fishes.push_back({ny, nx, p.cnt + 1});
            }
 
        }
    }
    if(fishes.size() > 0) return true;
    return false;
}
 
int main(void){
    scanf("%d", &N);
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            scanf("%d", map[i] + j);
            if(map[i][j] == 9){
                shark_y = i;
                shark_x = j;
                shark_size = 2;
                map[i][j] = 0;
            }
        }
    }
    vector<_pair> fishes;
    while(bfs(fishes)){
        sort(fishes.begin(), fishes.end(), cmp);
        shark_y = fishes[0].y;
        shark_x = fishes[0].x;
        total_second += fishes[0].cnt;
        eat_cnt++;
        map[shark_y][shark_x] = 0;
        if(eat_cnt == shark_size){
            eat_cnt = 0;
            shark_size++;
        }
        fishes.clear();
    }
    printf("%d", total_second);
 
}