[BOJ 16236] 아기 상어

# 문제

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

# 풀이

문제에 조건들이 은근히 많습니다.

현재 자신의 크기도 판단해야되고, 자기보다 크기가 작은 친구들의 위치를 구할때, 자신과 크기가 같은 친구들은 통과 되지만, 자신 보다 큰 친구들을 못지나가고....

또, 자신보다 작은 친구들을 탐색할때, 같은 거리에 있는 친구들이 있다면 맨 위, 왼쪽이 우선순위여야하고....

이렇게나 지켜야할 조건들이 은근 있어 까다로운 문제입니다.

저는 아기 상어의 위치와 정보를 구조체로 만들어 전역변수로 선언하여 계속해서 사용했습니다.

또, 물고기들의 위치와 사이즈도 구조체로 만들어 위부터 그것도 왼쪽에서 맵 입력을 받을 때마다 넣어 주었습니다.

(위로 인하여 위에 조건중 거리가 같은 물고기가 있을때 맨 위에 그것도 왼쪽인 물고기를 우선으로 하는 조건을 만족할 수있습니다.)

그 후 매번 엄마 상어의 도움을 청해야되는지 확인을 해보아야합니다.

확인 하는 함수는 checkingFishEat(87번째 줄) 에서 보이듯이 저장된 물고기들 중에 먹고 남은 물고기 즉, 먹지 못하는 물고기는 제외하고 다 먹었는지 확인을 계속적으로 해줍니다.

이제 먹이를 먹는 처리를 해주어야겠죠?

저는 먼저 지나갈 수 있는 자리를 BFS를 통해 돌려주었습니다.

매번 위치가 변하고, 크기도 변하기 때문에 매번마다 거리 맵을 만들어 주었습니다.(N의 크기가 20이하라 가능 한것 같습니다...)

맵을 만든 후에 자신이 먹을 수 있는 먹이중 가장 가까운 먹이를 먹어야하므로, BFS로 만들어준 맵을 참고하여 자신 보다 작고 가장 가까운 물고기를 찾습니다.

중요!!!!

여기서 중요한 점이 있습니다.

만약 먹을 물고기는 존재하는데, 주변에 큰 물고기들... 예를 들면

1	0	0	0
0	6	0	0
6	9	6	0
0	6	0	0

이렇게 둘러 쌓여있는 경우에는 못나가기 때문에 따로 처리를 해주어야합니다.

이것 때문에 꽤나 고생했습니다...역시..멍청한거같아요.. :(

계속해서 이동하며 물고기를 먹고, 먹은 물고기는 다음에 위에 계산을 하지 않도록 size 자체를 -1로 두어 걸러지게 처를 해주었습니다. 또한, 전체 맵 자체에도 없어지게 해놓았습니다. 이 후 이 행동을 반복하면서 답에다가 움직인 거리를 추가하면~ 끝~

# 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
struct Shark{
    int r,c;
    int size = 2;
    int cnt = 0;
};
 
struct Fish{
    int r,c;
    int size;
};
 
int N;
int sea[20][20];
Shark shark;
vector<Fish> fishs;
int ans = 0;
bool notMove = false;
 
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
void initTargetDist(int (*dist)[20]){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            dist[i][j] = 0;
        }
    }
}
void calcDist(int (*targetDist)[20] ){
    queue<pair<int, int>> q;
    q.push({shark.r,shark.c});
    targetDist[shark.r][shark.c] = 1;
    while(!q.empty()){
        int curR = q.front().first;
        int curC = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nr = curR + dr[i];
            int nc = curC + dc[i];
            if(nr < 0 || nr > N-1 || nc < 0 || nc > N-1) continue;
            if(targetDist[nr][nc] != 0) continue;
            if(sea[nr][nc] > shark.size) continue;
            q.push({nr,nc});
            targetDist[nr][nc] = targetDist[curR][curC] + 1;
        }
    }
}
 
void eatFishs(){
    int targetDist[20][20];
    initTargetDist(targetDist);
    calcDist(targetDist);
    int fishNum = -1;
    int finaldist = 10000;
    for(int i = 0; i < fishs.size(); i++){
        if(fishs[i].size == -1) continue;
        if(fishs[i].size < shark.size){
            int dist = targetDist[fishs[i].r][fishs[i].c];
            if(dist == 0) continue;
            if(finaldist > dist){
                finaldist = dist;
                fishNum = i;
            }
        }
    }
    if(finaldist == 10000){
        notMove = true;
        return;
    }
    ans += (finaldist-1);
    shark.r = fishs[fishNum].r;
    shark.c = fishs[fishNum].c;
    shark.cnt++;
    if(shark.cnt == shark.size){
        shark.size++;
        shark.cnt = 0;
    }
    fishs[fishNum].size = -1;
    sea[shark.r][shark.c] = 0;
}
 
bool checkingFishEat(){
    for(int i = 0; i < fishs.size(); i++){
        if(fishs[i].size > 0){
            if(fishs[i].size - shark.size >= 0){
                continue;
            }
            return false;
        }
    }
    return true;
}
 
int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> sea[i][j];
            if(sea[i][j] != 0){
                if(sea[i][j] == 9){
                    shark.r = i;
                    shark.c = j;
                    sea[i][j] = 0;
                }else{
                    Fish fish;
                    fish.r = i;
                    fish.c = j;
                    fish.size = sea[i][j];
                    fishs.push_back(fish);
                }
            }
        }
    }
    while(true){
        if(checkingFishEat() || notMove) break;
        eatFishs();
    }
    cout << ans << endl;
    return 0;
}