백준 16236번 아기 상어 문제 풀이

백준저지 16236번 아기 상어 문제 풀이입니다.

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

N값이 작으므로 bfs를 활용한 완전탐색으로 하나하나 시뮬레이션 해서 풀면 됩니다.

 

#include <stdio.h>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int dx[] = { +1, -1, +0, +0 };
const int dy[] = { +0, +0, +1, -1 };
int n;
struct Pos {
    int x, y;
    
    bool operator<(const struct Pos& rhs) const {
        return x != rhs.x ? x < rhs.x : y < rhs.y;
    }
    bool operator>(const struct Pos& rhs) const {
        return x != rhs.x ? x > rhs.x : y > rhs.y;
    }
};

typedef pair<int, Pos> State; //first -> 먹는데 걸리는 거리 / second->좌표
vector<State> eatable;

int field[21][21];
bool visit[21][21];
int shark_size, eat_left;
inline bool is_in(int x, int y) { return x >= 0 && y >= 0 && x < n && y < n; }
#define FOR(i, a, b) for (int i=a; i < b; i++)
void bfs(int x, int y) {
    visit[x][y] = true;
    queue<State> q;
    q.push({ 0, { x, y } });
    while (!q.empty()) {
        State s = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = s.second.x + dx[i];
            int ny = s.second.y + dy[i];
            int d = s.first;
            if (is_in(nx, ny)) {
                auto& f = field[nx][ny];
                auto& v = visit[nx][ny];
                if (!v) {
                    //방문 안한 경우
                    v = true;
                    if (f <= shark_size) {
                        q.push({ d + 1, { nx, ny } });
                        if (f > 0 && f < shark_size) {
                            eatable.push_back({ d + 1, { nx, ny } });
                        }
                    }
                }
            }
        }
    }
}

int main() {
#ifdef WIN32
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d", &n);
    Pos shark;
    shark_size = 2;
    eat_left = 2;

    int ans = 0;
    //get input
    FOR(i, 0, n) {
        FOR(j, 0, n) {
            scanf("%d", &field[i][j]);
            if (field[i][j] == 9) {
                shark.x = i;
                shark.y = j;
                field[i][j] = 0;
            }
        }
    }

    while (true) {
        memset(visit, 0, sizeof(visit));
        eatable.clear();
        bfs(shark.x, shark.y);
        sort(eatable.begin(), eatable.end());
        if (eatable.size() == 0) break;

        int distance = eatable[0].first;
        int nx = eatable[0].second.x;
        int ny = eatable[0].second.y;
        shark.x = nx;
        shark.y = ny;
        field[nx][ny] = 0;
        --eat_left;
        if (eat_left <= 0) {
            shark_size++;
            eat_left = shark_size;
        }

        ans += distance;
        
    }
    printf("%d\n", ans);
}