백준 16236 - 아기상어

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

16236번: 아기 상어

문제 설명

---

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 그리고 한칸에는 최대 한마리만 존재 가능합니다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다.

아기상어 RULE

1. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
2. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.
3. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.
(따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.)

아기 상어가 어디로 이동할지 결정 RULE

1. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
2. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
3. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
4. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
5. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다.

즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.

이때, 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 시간을 구하는 문제이다!!!

 

 

접근 방식

---

시뮬레이션 문제로 여러 조건들이 나와있으므로 Struct를 이용하여 조건을 통합하여 관리할 수 있도록 하자!!!

두번째로는 규칙을 코드로 구현하자

1. 먼저 아기 상어가 먹을 수 있는 물고기를 찾고 이에 해당되는 Depth를 구하여 관리한다.

2. 조건대로 가장 가까운것을 최우선, 그 다음 위에 있는 물고기, 모두 만족한다면 왼쪽에 있는 물고기 순으로 잡아먹는다.!!!!

설명은 코드에 주석으로 상세히 설명 해놓았습니다 *0*

 

 

코드

---

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define MAX 20
using namespace std;
 
typedef struct{
    int y;
    int x;
    int Size;
    int Eat;
    int Time;
}Shark;
 
typedef struct{
    int y;
    int x;
    int Dist;
}Food;
 
int n;
int map[MAX][MAX];
bool visit[MAX][MAX];
 
Shark S;
vector<Food> V;
 
int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1 ,-1 ,0 ,0 };

bool inside(int ny,int nx){
    return (ny >= 0 && nx >= 0 && ny < n && nx < n);
}

void Bfs(int a, int b){
    queue<pair<pair<int, int>, int> > Q;
    Q.push(make_pair(make_pair(a, b), 0));
    visit[a][b] = true;
    while (!Q.empty()){
        int y = Q.front().first.first;
        int x = Q.front().first.second;
        int Dist = Q.front().second;
        Q.pop();
        for (int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            //안에 있는지 판단
            if (inside(ny,nx)){
                //만일 방문 하지 않았다면
                if (visit[ny][nx] == false){
                    //다음의 경우의수를 나눈다 0인경우 지나갈수 있고 dist+1
                    if (map[ny][nx] == 0){
                        visit[ny][nx] = true;
                        //거리만 +1을 하여 넣어준다
                        Q.push(make_pair(make_pair(ny, nx), Dist + 1));
                    }
                    else if (map[ny][nx] < S.Size){
                        //만일 먹을 수 있다면 -지금의 상황을 food에 저장 dist+1
                        Food Temp;
                        Temp.y = ny;
                        Temp.x = nx;
                        Temp.Dist = Dist + 1;
                        //V백터에 먹을수 있은 정보를 저장
                        V.push_back(Temp);
                        visit[ny][nx] = true;
                        //방문 체크
                        //queue에 삽입
                        Q.push(make_pair(make_pair(ny, nx), Dist + 1));
                    }
                    //사이즈가 같은 경우 0과같이 방문 처리 및 큐에 저장 
                    else if (map[ny][nx] == S.Size){
                        visit[ny][nx] = true;
                        Q.push(make_pair(make_pair(ny, nx), Dist + 1));
                    }
                }
            }
        }
    }
}
 
bool Sorting_Shark(Food A, Food B){
    //거리가 작으면 true 아니면 false
    if (A.Dist <= B.Dist){
        //거리가 같을때 비교 순위
        if (A.Dist == B.Dist){
            //위쪽에 존재하는 물고기가 우선 순위
            if (A.y <= B.y){
                if (A.y == B.y){
                    //같다면 왼쪽에 있는것이 우선 순위
                    if (A.x < B.x){
                        return true;}
                    return false;}
                return true;}
            return false;}
        return true;}
    return false;
}
 
void selectAndEat(){
    while (1){
        V.clear();
        memset(visit, false, sizeof(visit));
        Bfs(S.y, S.x);
        if (V.size() == 0){
            cout << S.Time << "\n";
            break;
        }
        else if (V.size() == 1){
            map[V[0].y][V[0].x] = 9;
            map[S.y][S.x] = 0;
            S.y = V[0].y;
            S.x = V[0].x;
            S.Eat++;
            S.Time = S.Time + V[0].Dist;
 
            if (S.Eat == S.Size){
                S.Eat = 0;
                S.Size++;
            }
        }
        else{
            sort(V.begin(), V.end(), Sorting_Shark);
            map[V[0].y][V[0].x] = 9;
            map[S.y][S.x] = 0;
            S.y = V[0].y;
            S.x = V[0].x;
            S.Eat++;
            S.Time = S.Time + V[0].Dist;
 
            if (S.Eat == S.Size){
                S.Eat = 0;
                S.Size++;
            }
        }
    }
} 
int main(void){
    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){
                S.y = i;
                S.x = j;
                S.Size = 2;
                S.Eat = 0;
                S.Time = 0;
            }
        }
    }
    selectAndEat();
    return 0;
}

funny algorithms *0*~