[C++] 백준 BOJ 16236 아기 상어

문제링크 : https://noj.am/16236

BFS로 그냥 풀면 간단한 문제일 줄 알았는데 개인적으로는 약간 고민을 많이 했던 문제이다.

아기 상어가 물고기를 먹을 때 먹을 수 있는 물고기 중에서 가장 가까운 아무거나 먹는게 아니라 가장 위, 가장 왼쪽에 있는 것을 먹어야 한다는 까다로운 조건이 붙기 때문이다.

이를 해결하기 위하여 우선순위 큐 + BFS를 사용하여 해결하였다.

BFS를 위해 필요한 큐를 우선순위 큐로 사용하였고

큐에 담길 데이터는 연산자 오버로딩을 통하여 아래와 같이 min heap이 구성되는 방식이다.

① BFS 레벨이 작은 순서 (상어의 이동 거리)

② x의 좌표가 작은 순서

③ y의 좌표가 작은 순서

// BOJ_16236 아기 상어
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
 
struct pt {
    int x, y;
    int len; // 상어의 이동거리
 
    const bool operator<(const pt &p) const {
        // 1. len 비교
        if (len == p.len) {
            // 2. x 좌표 비교
            if (x == p.x)
                // 3. y 좌표 비교
                return y > p.y;
            return x > p.x;
        }
        return len > p.len;
    }
};
 
struct shark {
    int x, y;
    int cnt = 0;
    int size = 2;
 
    shark() {}
 
    shark(int x, int y) {
        this->x = x;
        this->y = y;
    }
 
    void sizeUp() {
        cnt = 0;
        size++;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int N;
    cin >> N;
 
    vector<vector<int> > arr(N + 2, vector<int>(N + 2, INT32_MAX));
    vector<vector<bool> > visited(N + 2, vector<bool>(N + 2, false));
 
    shark baby;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 9) {
                baby = {i, j}; // 상어 좌표 저장
                arr[i][j] = 0;  // 해당 자리는 빈칸으로
            }
        }
    }
 
    int result = 0;
    priority_queue<pt> Q;
    Q.push({baby.x, baby.y, 0});
    visited[baby.x][baby.y] = true;
 
    while (!Q.empty()) {
        pt cur = Q.top();
        Q.pop();
        // 먹을 수 있는 물고기라면
        if (arr[cur.x][cur.y] != 0 && baby.size > arr[cur.x][cur.y]) {
            // 좌표 이동
            baby.x = cur.x;
            baby.y = cur.y;
            // 물고기 냠냠
            baby.cnt++;
            arr[cur.x][cur.y] = 0;
            // 물고기 먹은 갯수가 몸집에 도달시
            if (baby.cnt >= baby.size)
                baby.sizeUp();
            // 방문 초기화
            visited = vector<vector<bool> >(N + 2, vector<bool>(N + 2, false));
            // 큐 초기화
            while(!Q.empty()) Q.pop();
            // 정답 저장
            result = cur.len;
        }
        for (int i = 0; i < 4; i++) {
            // 다음 4방향 이동 좌표
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            // 아기 상어의 사이즈보다 크거나 방문했으면
            if (arr[nx][ny] > baby.size || visited[nx][ny])
                continue;
            // 방문 체크
            visited[nx][ny] = true;
            Q.push({nx, ny, cur.len + 1});
        }
    }
    cout << result;
 
    return 0;
}