[BOJ] - 16236. 아기 상어

[URL]

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

16236번: 아기 상어

 

[풀이 과정]

* BFS + 시뮬

 

1. 아기 상어가 먹을 수 있는 물고기 개수를 구한다.

   먹을 수 있는 물고기 개수 = 0   -> 종료

   먹을 수 있는 물고기 개수 = 1   -> 그 위치(nearX, nearY)로 먹으러 간다

   먹을 수 있는 물고기 개수 > 1   -> 가장 가까운 물고기 구한다.  ->  그 위치(nearX, nearY)로 먹으러 간다

 

2. findNearFish()

  현재 (baby.x, baby.y) 위치로 부터 이동 가능 하며, 조건 (거리 같을때 가장 위쪽, 같으면 가장 왼쪽)을 가지고

  BFS탐색으로 가장 가까운 곳을 구한다. --> (nearX, nearY)

 

3. go()

목표 위치로 이동, map[][] 업데이트, 아기상어 현재 위치(baby.x, baby.y)  갱신, 아기상어 사이즈 갱신

 

 

 

[소스 코드]

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
struct BabyShark {
    int x;
    int y;
    int size;
    int sizeCheck;        // 변하는 상어사이즈 관리
};
BabyShark baby;
 
struct Fish {
    int x;
    int y;
    int dist;
};
 
int N;
int map[21][21];
int nearX = 0, nearY = 0, nearDist = 0;
 
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int resCnt = 0;
 
// 물고기 정렬 (같은 거리면 가장 위쪽, 가장 위쪽에서도 여러마리면 가장 왼쪽)
bool cmp(const Fish &a, const Fish &b) {
    if (a.x == b.x)
        return a.y < b.y;
    else
        return a.x < b.x;
}
 
// 초기화 & 입력
void init() {
    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)
            {
                baby.x = i;
                baby.y = j;
                baby.size = 2;
                baby.sizeCheck = 2;
                map[i][j] = 0;
            }
        }
    }
}
 
// 먹을 수 있는 물고기 갯수 구하기(수정 필요)
int findFish()
{
    int fishCnt = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] != 0 && map[i][j] < baby.size)
            {
                fishCnt++;
                nearX = i;
                nearY = j;
            }
        }
    }
 
    return fishCnt;
}
 
// 현재 아기상어 위치로 부터 destX, destY까지 이동할 수 있는 거리
int BFS(int destX, int destY) {
 
    queue <pair<int, int>> q;
    bool visited[21][21] = { 0, };
    int dist[21][21] = { 0, };
 
 
    visited[baby.x][baby.y] = true;
    dist[baby.x][baby.y] = 0;
    q.push(make_pair(baby.x, baby.y));
 
    while (!q.empty())
    {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++)
        {
            int nx = cx + dx[k];
            int ny = cy + dy[k];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (map[nx][ny] <= baby.size && visited[nx][ny] == false)
                {
                    visited[nx][ny] = true;
                    dist[nx][ny] = dist[cx][cy] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
 
    return dist[destX][destY];
}
 
 
// 가장 가까운 물고기 찾자 
void findNearFish() {
    vector <Fish> v;
 
    int Min = 987654;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] != 0 && map[i][j] < baby.size)
            {
                int tempDist = BFS(i, j);
 
                if (Min >= tempDist && tempDist > 0)
                {
                    Min = tempDist;
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] != 0 && map[i][j] < baby.size)
            {
                if (BFS(i, j) == Min)
                {
                    Fish temp;
                    temp.x = i;
                    temp.y = j;
                    temp.dist = Min;
 
                    v.push_back(temp);
                }
            }
        }
    }
 
    if (v.size() != 0)
    {
        sort(v.begin(), v.end(), cmp);
 
        nearX = v.front().x;
        nearY = v.front().y;
        nearDist = v.front().dist;
    }
    else
    {
        nearDist = 0;
    }
 
    v.clear();
}
 
void go(int destX, int destY, int nearDist)        // 목적지 x, y로 이동하여 물고기 먹음!
{
    resCnt += nearDist;
 
    baby.x = destX;
    baby.y = destY;
 
    map[destX][destY] = 0;
 
    baby.sizeCheck--;
    if (baby.sizeCheck == 0)
    {
        baby.size++;
        baby.sizeCheck = baby.size;
    }
}
 
int main() {
    init();
 
    while (true)
    {
        int fishCnt = findFish();
 
        // 1.없는 경우
        if (fishCnt == 0)
            break;
 
        // 2.한 마리인 경우
        if (fishCnt == 1)
        {
            nearDist = BFS(nearX, nearY);
            if (nearDist == 0)
                break;
            else
                go(nearX, nearY, nearDist);            // 먹으로 출발
        }
 
        // 3.여러 마리인 경우
        if (fishCnt > 1)
        {
            findNearFish();            // 찾자 가장 가까운 물고기
 
            if (nearDist == 0)
                break;
            else
                go(nearX, nearY, nearDist);            // 먹으로 출발
        }
    }
 
    printf("%d\n", resCnt);
 
    return 0;
}