[알고리즘] 백준 16236 아기상어

16236 아기상어

가장 가까운 거리의 물고기를 먹으면서 상어가 이동하게 되므로 bfs를 이용하여 가장 가까운 물고기들을 찾아주었으며 이를 found벡터에 저장하였다. 벡터에 저장하면 같은 거리의 여러 물고기들을 헨들링할 수 있었다.

go()함수를 통해 가장 가까운 물고기 벡터를 만들고 벡터의 크기와 물고기까지의 거리를 리턴한다.
이후, 정렬을 하면 가장 처음에 있는 물고기가 문제의 조건을 만족하는 다음 이동 위치이다. 아기상어를 해당 위치로 이동시키고 아기상어의 크기를 증가시켜주는 조건을 추가해준 뒤 ret에 거리를 더해준다.

위 내용을 더이상 먹을 수 있는 상어가 없을 때까지 반복하면 된다.

풀이

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n,arr[21][21],visited[21][21];
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
queue<pair<int,int>> q;

pair<int,int> shark;
vector<pair<int,int>> found;
int shark_size = 2;
int feeded = 0;

pair<int,int> go(){
    memset(visited,-1,sizeof(visited));
    found.clear();

    int found_size = 0;
    q.push(shark);
    visited[shark.first][shark.second] = 0;
    while(q.size()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        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 || visited[nx][ny] != -1) continue;
            if(arr[nx][ny] > shark_size) continue;
            visited[nx][ny] = visited[x][y] + 1;
            q.push({nx,ny});

            if(arr[nx][ny] == 0 || arr[nx][ny] >= shark_size) continue;
            if(found_size == 0){
                found_size = visited[nx][ny];
                found.push_back({nx,ny});
            }else if(visited[nx][ny] == found_size){
                found.push_back({nx,ny});
            }
        }
    }
    return {found.size(),found_size};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    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){
                shark = {i,j};
                arr[i][j] = 0;
            } 
        }
    }

    int ret = 0;

    while(true){
        pair<int,int> check = go();
        if(!check.first) break;
        sort(found.begin(),found.end());
        pair<int,int> next = found[0];
        shark = next;
        arr[shark.first][shark.second] = 0;
        feeded++;
        if(shark_size == feeded){
            shark_size++;
            feeded = 0;
        }
        ret += check.second;
    }
    cout<<ret;
}