[알고리즘 풀이 분석] BOJ 16236 아기상어

오늘은 BOJ 16236 아기상어 문제를 풀어보았다! 시뮬레이션 문제였고, 중간에 BFS 도 함께 사용하였다!
요 몇일동안 푼 문제들이 약간 비슷한 흐름을 유지하는 듯 하넹,,?

BOJ 16236 아기상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
• 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
• 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입출력

나의 풀이

이 문제도 어제 푼 BOJ 2573 빙산 문제와 유사하게 크게 두 파트로 이루어져 있다고 판단했다.

먹을 물고기를 결정 + 결정한 물고기 먹기

사실 후자는 비교적 간단한 과정이고 사실상 먹을 물고기를 결정하는 것이 이 문제의 핵심인 것 같다.

먹을 물고기를 결정하기

기본적으로 NxN 배열로 된 그래프 탐색 과정이다.
탐색 과정에서 시간을 줄이기 위해 N^2 개의 2차원 배열을 모두 탐색하지 않고 먹이가 될 수 있는 물고기들만 따로 배열 fishes 에 저장하고, 그 배열에 대해서만 검사를 진행 했다.

fishes 가 비어있지 않다면 각 물고기들이 현재 상어의 위치로부터 도달할 수 있는지를 isCatchable 함수로 검사했고 isCatchable 함수에선 BFS 를 사용해서 탐색했다. 빠른 탐색을 위해 BFS를 선택했고 어제 푼 문제에서도 BFS 를 적용했기에 수월하게 작성할 수 있었지만 한번 DFS로 해볼까,,? 했는데 오마이갓;; DFS 살짝 잊어버린 기억 ;; 내일은 DFS 간다~!

배열 fishes 의 원소들별로 isCatchable 검사하고 검사하면서 경로 값도 동시에 계산한다. 검사 결과, 도달 가능하면 해당 물고기의 좌표와 거리 값을 함께 묶어 배열 eatable 에 저장한다.

여기서 만약 배열 eatable 에 들어간 물고기가 없다면 아기상어가 더이상 먹을 수 있는 물고기가 없다는 뜻이므로 엄마상어 호출~~ 반복문을 끝내고 소요된 시간을 반환한다!

이후 eatable 를 주어진 조건에 맞게 정렬 (거리가 가까운 순 -> 행이 작은 순 -> 열이 작은 순)하면 eatable[0]이 최종적으로 먹을 물고기로 정해지게 된다.

물고기 먹기

최종적으로 정해진 물고기 eatable[0] 의 자리로 상어의 위치를 수정하고 원래 상어가 있던 칸은 빈칸으로 수정한다.

상어가 먹은 물고기 수를 증가시키고 이 값이 상어의 몸 사이즈와 동일하면 상어의 사이즈를 증가, 먹은 물고기 수는 다시 0으로 초기화 시킨다! (이부분을 잊을 뻔 했다..!)

이후 배열 fishes를 초기화 하고 새롭게 변경된 NxN 배열에서 먹이가 될 수 있는 물고기들로 채워 다시 먹을 물고기를 탐색하는 과정을 반복하도록 하였다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

// 먹을 물고기 후보 정렬 기준
bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    if (a.second != b.second){  // 거리 짧은거
        return a.second < b.second;
    }else {
        if (a.first.first != b.first.first){
            return a.first.first < b.first.first;  // 행 빠른거
        }else{
            return a.first.second < b.first.second;  // 열 빠른거
        }
    }
}

// shark -> fish 까지 dfs 탐색 하면서 도달 가능하면 true
bool isCatchable(vector<vector<int>> sea, pair<int, int> shark, pair<int, int> fish, int sharkSize, int & cost){
    bool able = false;

    vector<vector<bool>> visited(sea.size(), vector<bool>(sea.size()));

    queue<pair<pair<int, int>, int>> points;
    points.push(make_pair(shark, 0));
    visited[shark.first][shark.second] = true;

    while (!points.empty()){
        pair<pair<int, int>, int> loc = points.front();
        points.pop();

        if (loc.first == fish){
            if (!able) able = true;

            if (cost > loc.second) {
                cost = loc.second;
            }

            continue;
        }

        for (int i = 0; i < 4; ++i) {
            int r = loc.first.first + dy[i];
            int c = loc.first.second + dx[i];

            if (r>=0 && r<sea.size() && c>=0 && c<sea.size()){
                if (sea[r][c] <= sharkSize && !visited[r][c]){
                    visited[r][c] = true;
                    points.push(make_pair(make_pair(r, c), loc.second + 1));
                }
            }
        }
    }

    return able;
}

int getBabySharkTime(vector<vector<int>> sea, vector<pair<int, int>> fishes, pair<int, int> shark){
    int N = sea.size();
    int second = 0;
    int sharkSize = 2;
    int yum = 0;

    while (!fishes.empty()){
        // 가서 먹을 수 있는 물고기 골라내기
        vector<pair<pair<int, int>, int>> eatable;

        for (int i = 0; i < fishes.size(); ++i) {
            int dist = 2147483647;
            // 도달 가능한지 확인 - BFS
            if (isCatchable(sea, shark, fishes[i], sharkSize, dist)){
                eatable.push_back(make_pair(fishes[i], dist));
            }
        }

        // 엄마 상어 호출
        if (eatable.size() == 0) break;

        // eatable 물고기들을 기준에 맞게 정렬 -> eatable[0] 가 먹을놈
        if (eatable.size() > 1) {
            sort(eatable.begin(), eatable.end(), comp);
        }

        // 물고기 먹으러
        sea[shark.first][shark.second] = 0;
        shark = eatable[0].first;
        second += eatable[0].second;
        sea[shark.first][shark.second] = 9;

        // 먹고 사이즈 갱신 확인
        yum++;
        if (yum == sharkSize){
            yum = 0;
            sharkSize++;
        }

        // 새롭게 먹을 수 있는 물고기 확인
        fishes.clear();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (sea[i][j] >= 1 && sea[i][j] <= 6 && sea[i][j] < sharkSize){
                    fishes.push_back(make_pair(i, j));
                }
            }
        }
    }


    return second;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin>>N;

    vector<vector<int>> sea(N, vector<int>(N, 0));
    vector<pair<int, int>> fishes;
    pair<int, int> shark;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin>>sea[i][j];

            if (sea[i][j] == 9) {
                shark = make_pair(i, j);
            }else if (sea[i][j] >= 1 && sea[i][j]<=6 && sea[i][j] < 2){
                fishes.push_back(make_pair(i,j));
            }
        }
    }

    int second = getBabySharkTime(sea, fishes, shark);

    cout<<second;


    return 0;
}

일주일? 전에 처음으로 시뮬레이션을 풀어봤을 때는 이거보다 훨씬 어렵게 느껴졌던 것 같은데, 오늘은 조금 더 수월했다!
지금까지 느낀 시뮬레이션은,, 집중력, 꼼꼼함 싸움인 것 같다..!