아기상어 16236번 [백준]

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

16236번: 아기 상어

 

bfs을 활용하여 푸는 문제입니다.

#include<bits/stdc++.h>
#include<sys/types.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(ll i=0;i<j;i++)
#define pii pair<int,int>
#define ff first
#define ss second

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

int n;
vector<vector<int>> v;
pii shark;
vector<vector<int>> visited;
int size2 = 2;
int cnt = 0;
int min_x = 99;
int min_y = 99;
int min_dist = 11111;

int search() {
    queue<pii > q;
    q.push(shark);

    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        rep(i, 4) {
            int _x = cur.ff + dx[i];
            int _y = cur.ss + dy[i];
            if (_x < 0 || _y < 0 || _x >= n || _y >= n)continue;
            if (visited[_x][_y] != 0 || v[_x][_y] > size2)continue;
            visited[_x][_y] = visited[cur.ff][cur.ss] + 1;
            if (v[_x][_y] < size2 && v[_x][_y] != 0) {
                if (min_dist > visited[_x][_y]) {
                    min_x = _x;
                    min_y = _y;
                    min_dist = visited[_x][_y];
                } else if (min_dist == visited[_x][_y]) {
                    if (min_x == _x) {
                        if (min_y > _y) {
                            min_x = _x;
                            min_y = _y;
                        }
                    } else if (min_x > _x) {
                        min_x = _x;
                        min_y = _y;
                    }
                }
            }
            q.push({_x, _y});
        }
    }
    cnt++;
    if (min_x == 99)return -1;
    shark = {min_x, min_y};
    int ans = visited[min_x][min_y];
    v[min_x][min_y] = 0;
    return ans;
}

void solve() {
    cin >> n;
    v = vector<vector<int>>(n, vector<int>(n));
    visited = vector<vector<int>>(n, vector<int>(n, 0));
    rep(i, n)rep(j, n) {
            cin >> v[i][j];
            if (v[i][j] == 9)shark = {i, j};
        }
    v[shark.ff][shark.ss] = 0;
    int ans = 0;
    while (1) {
        visited = vector<vector<int>>(n, vector<int>(n, 0));
        min_x = 99;
        min_y = 99;
        min_dist = 999;
        int s = search();
        if (cnt == size2) {
            cnt = 0;
            size2++;
        }
        if (s == -1) {
            cout << ans << endl;
            return;
        }
        ans += s;
    }
}

int main() {
    fast_io;
    solve();
    return 0;
}