[ 백준 16236 ] 아기상어

문제

문제 이동

문제 설명

• 아기 상어가 거리가 가까운 물고기를 어떻게 찾아야 할까 ?

  • BFS ( bool 방문 배열 )

• BFS 를 통해 물고기를 찾는 과정에서 어떤 자료구조를 사용해야 할까 ?

  • queue pair

• (✅)거리가 같은 물고기들이 많다면 가장 위쪽 , 가장 왼쪽인 물고기를 어떻게 알 수 있을까 ?

  • BFS 를 돌면서 물고기들을 만날때마다 vector pair 에 저장해두어 sort 를 이용.

 

구현

1. 초기 queue 에 상어의 위치를 넣고 , 방문 배열을 false 로 만들어 준다.

2. queue 의 size 동안

   queue의 front 좌표에 물고기를 먹을 수 있다면 => vector 용기에 담아줌

   물고기를 먹을 수 없다면

   (1). 배열 범위 넘지 않고

   (2). 방문 배열이 false 이고

   (3). 상어 크기보다 작거나 같다면 !!!!!! => queue 에 방향 담아줌.

3. 만약 vector 의 size 가 1보다 같거나 크다면 ( 물고기 먹방이 시작되는거임 )

   sort ( vector )을 해준뒤 vector 맨 앞의 front 값으로

   아기상어의 새로운 시작을 위해

   (1). 아기 상어가 먹은 먹이 공간(?) 0으로 만들고

   (2). vector 다 비우고,

   (3). queue에는 현재 아기 상어의 좌표만 담아주고,

   (4). 방문배열 현재 아기 상어 true 로 만들고

   (5). 아기 상어가 먹은 물고기 +1

   (6). 최종 시간(최종 정답) += cnt // 아기 상어가 물고기 먹으러 갔던 시간들

    

   만약 아기 상어가 먹은 물고기 == 아기 상어 크기 라면 아기 상어 크기 +1 과 먹은 물고기는 0으로 초기화

    

4. cnt ++ // 아기 상어가 물고기 먹으러 갔던 시간

 

2, 3번의 과정을 queue 가 비었을 때까지 반복해주면 된다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
​
int n;
int arr[21][21];
bool check[21][21];
​
queue<pair<int, int>> q;//4 direction
vector<pair<int, int>> fish;//shark eat fish
​
int cnt = 0;
int sec = 0;
int shark = 2;
int feed = 0;
​
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
​
void Input()
{
    cin >> n;
    int data;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> data;
            if (data == 9) {
                arr[i][j] = 0;
                q.push(make_pair(i, j));
                check[i][j] = true;
            }
            else arr[i][j] = data;
        }
    }
}
​
void BFS()
{
    while (!q.empty())
    {
        int size = q.size();
​
        for (int i = 0; i < size; i++)
        {
            int x = q.front().first;
            int y = q.front().second;
​
            q.pop(); 
            if (arr[x][y] < shark && arr[x][y] != 0)
            {
                fish.push_back(make_pair(x, y));//eat fish
            }
            else
            {
                for (int k = 0; k < 4; k++)
                {
                    if (x + dx[k] >= 0 && x + dx[k] < n&&y + dy[k] >= 0 && y + dy[k] < n) {//범위 넘지 않음
                        if (check[x + dx[k]][y + dy[k]] == false && arr[x+dx[k]][y+dy[k]]<=shark) {
                            //방문 배열 false and 상어크기보다 작거나 같음(그래야 지나갈 수 있음)
                            check[x + dx[k]][y + dy[k]] = true;
                            q.push(make_pair(x + dx[k], y + dy[k]));
                        }
                    }
                }
            }//else
        }//for
        if (fish.size() >= 1)//먹이 존재 !
        {
            sec += cnt;
            cnt = -1;
​
            for (int a = 0; a < n; a++)
                for (int b = 0; b < n; b++)
                    check[a][b] = false;
​
            sort(fish.begin(), fish.end());
            int nx = fish.front().first;
            int ny = fish.front().second;
​
            arr[nx][ny] = 0;
​
            while (!q.empty())q.pop();
            q.push(make_pair(nx, ny));
​
            while (!fish.empty()) fish.pop_back();
​
            feed++;
​
            if (feed == shark)//상어 크기만큼 먹이가 있다면 상어 크기는 +1 증가
            {
                shark++;
                feed = 0;
            }
        }
        cnt++;
    }//while
}
​
void Solve()
{
    Input();
    BFS();
}
​
int main()
{
    Solve();
    cout << sec << endl;
}