[16236번] 아기 상어

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. bfs

이 문제는 조건만 잘 생각하면 쉽게 해결 할 수 있다.

1. 상어는 자신보다 작거나 같은 크기의 상어가 있는 곳을 움직 일 수 있다.

2. 상어는 자신보다 작은 것만 먹을 수 있다.

3. 상어는 아래 정렬조건을 가진다.

- 거리가 가장 가까운 물고기를 먹으러 간다.

- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

사실 정렬은 pair를 이용하여 거리,y좌표,x좌표를 담고 sort를 하면 알아서 정렬되도록 조건이 되어있다.

자신이 먹을 수 있는 상어를 모두 shark 벡터에 담고 정렬 한 후 벡터가 비어있다면 INF를 리턴, 그 외에는 벡터 첫번째 값을 리턴한다.

그리고 BFS의 리턴값이 INF라면 엄마 상어를 부르면 되고(종료)

BFS값이 존재한다면 그게 최단 거리에 있는 먹을 수 있는 상어를 의미하므로 먹이고 다음 BFS를 진행하면 된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <memory.h>
 
#define INF 987654321
using namespace std;
 
typedef pair<int, int> pii;
 
int arr[22][22];
int dy[4] = { -1,0,0,1 };
int dx[4] = { 0,-1,1,0 };
bool visit[22][22];
 
int n;
int sy, sx, sSize = 2, eat;
int ans;
 
pair<pii, pii> bfs() {
    memset(visit, 0, sizeof(visit));
 
    queue<pair<pii, int> > q;
    q.push({ {sy,sx}, 0 });
 
    vector<pair<int, pii>> shark;
 
    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int dist = q.front().second;
        q.pop();
 
        if (arr[y][x] != 0 && arr[y][x] < sSize) 
            shark.push_back({ dist,{ y,x } });
 
        if (visit[y][x])
            continue;
 
        visit[y][x] = true;
 
        for (int i = 0; i < 4; i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;
 
            if ((0 <= ny && ny < n) && (0 <= nx && nx < n) && arr[ny][nx] <= sSize)
                q.push({ {ny,nx}, dist + 1 });
        }
    }
 
    if(shark.empty())
        return{ { INF, INF } , { INF, INF } };
 
    sort(shark.begin(), shark.end());
    
    int dist = shark[0].first;
    int y = shark[0].second.first;
    int x = shark[0].second.second;
    int size = arr[y][x];
    return{ {y,x},{dist,size} };
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 9)
                sy = i, sx = j, arr[i][j] = 0;
        }
 
    while (1) {
        pair<pii, pii> tmp = bfs();
        if (tmp.second.first == INF)
            break;
 
        int y = tmp.first.first;
        int x = tmp.first.second;
        int dist = tmp.second.first;
        int size = tmp.second.second;
 
        ans += dist;
 
        sy = y;
        sx = x;
        eat++;
        arr[y][x] = 0;
        if (eat == sSize) 
            sSize++, eat = 0;
    }
 
    printf("%d\n", ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>