[BOJ 16236] 아기상어

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

풀이법 / 유의점

기본적인 BFS문제로, 먹을 수 있는 물고기가 없을때까지 BFS탐색을 반복해주면 된다.

이때 우선적으로 가장 가까운, 가장 위쪽의, 가장 왼쪽의 물고기를 우선적으로 먹어야하니,
vector<pair<int, pair<int, int>>> food에 먹을 수 있는 물고기를 모두 저장한 뒤 정렬하면, 별도의 처리 없이도 조건에 부합하는 물고기가 맨 앞에 위치하게 된다.

물고기를 먹을때마다, 해당칸에 아기상어를 옮겨줘야하고,
각 칸의 크기를 통해 BFS처리가 진행되니, 시작부터 아기상어 위치에 해당하는 9값은 0으로 바꾼 뒤 진행하였다(추후 크기 비교시, 9를 예외처리하거나, 먹이의 위치에 해당하는 값을 9로 바꾸고.. 원래 있던 위치는 0으로 바꾸는 식의 처리가 귀찮았음.)

source code

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

using namespace std;

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, -1, 0, 1};

vector<vector<int>> v;
pair<int, int> p;
int ans = 0;
int big = 2;
int cnt = 0;
int n;

bool in(int r, int c){
    return (0 <= r && r < n) && (0 <= c && c < n);
}

bool bfs(){
    queue<pair<int, int>> q;
    vector<pair<int, pair<int, int>>> food;
    vector<vector<bool>> visit(n, vector<bool>(n));
    vector<vector<int>> dist(n, vector<int>(n));

    q.push(p); 
    visit[p.first][p.second] = true;

    while(!q.empty()){
        auto [cur_r, cur_c] = q.front();
        for(int d = 0; d < 4; d++){
            int nxt_r = cur_r + dr[d];
            int nxt_c = cur_c + dc[d];

            if(!in(nxt_r, nxt_c)) continue;
            if(visit[nxt_r][nxt_c]) continue; // 이미 방문한 곳이라면? continue; 

            visit[nxt_r][nxt_c] = true; // 방문을 true로.

            if(v[nxt_r][nxt_c] > big) continue; // 거기 물고기가 더 크다면? 탐색 필요 없음.

            dist[nxt_r][nxt_c] = dist[cur_r][cur_c] + 1; // 더 큰 경우는 없으니, 해당 지역의 거리를 기록
            q.push(make_pair(nxt_r, nxt_c)); // 거기를 기준으로.. 또 탐색하기.

            if(0 < v[nxt_r][nxt_c] && v[nxt_r][nxt_c] < big){ // 거기가 내가 먹을 수 있는 곳이라면? food에 추가
                food.push_back(make_pair(dist[nxt_r][nxt_c], make_pair(nxt_r, nxt_c)));
            }
        }
        q.pop();
    }
    if(food.empty()) return false;
    else{
        sort(food.begin(), food.end());
        auto [dist, pos] = food[0];
        p = pos;
        ans += dist;
        cnt ++;
        v[p.first][p.second] = 0;
        if(cnt == big){
            cnt = 0; big ++;
        }
        return true;
    }
}
void print_map(){
    for(int r = 0; r < n; r++){
        for(int c = 0; c < n; c++){
            cout << v[r][c] << " ";
        }
        cout << endl;
    }
}
int main(){
    cin >> n;
    v.assign(n, vector<int>(n));
    for(int r = 0; r < n; r++)
    for(int c = 0; c < n; c++){
        cin >> v[r][c];
        if(v[r][c] == 9){
            p = make_pair(r, c);
            v[r][c] = 0;
        }
    }

    while(bfs());
    cout << ans;

}