아기 상어 16236 - 2 (백준으로 C++ 공부하기 37일차)

문제

16236번: 아기 상어

생각

최대한으로 다시 풀어봤지만 특정한 맵에서는 작동을 안 한다

상, 좌, 우, 하 순으로 이동을 하게 만들었지만 다음과 같은 맵에서는 문제에서 원하는 대로 이동하지 않는다.

4     
0 9 0 1
1 0 0 0 
0 0 0 0
0 0 0 0 
(y, x) = 1, 0
(y, x) = 0, 3

(1, 0)을 먼저 가는 게 아니라 (0, 3)을 먼저 가야 한다.

이는 그냥 큐로는 불가능한 것 같다.

지난번에 올린 것처럼 우선순위 큐를 이용하여 push와 동시에 정렬시켜야 한다.

코드

아래는 최대한의 코드이다.

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int dx[4] = { 0, -1, 1, 0 };
int dy[4] = { -1, 0, 0, 1 };
int map[21][21];
int vst[21][21] ={0, };
int sty, stx;

int main() {
    int n; cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> map[i][j];
            if(map[i][j] == 9) {
                sty = i;
                stx = j;
                map[i][j] = 0;
            }
        }
    }

    int size = 2;
    int sum = 0;
    int fishcnt = 0;
    int cnt = 0;
    //y, x, cnt
    queue<pair<pair<int, int>, int>> q;
    q.push({{sty, stx}, cnt});
    vst[sty][stx] = true;
    while(!q.empty()) {
        auto[cy, cx] = q.front().first;
        cnt =  q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny < 0 || nx < 0 || ny > n - 1 || nx > n - 1 || map[ny][nx] > size) continue;
            //Edible & not zero
            if(map[ny][nx] < size && map[ny][nx] != 0 && !vst[ny][nx]) {
                memset(vst, false, sizeof(vst));
                vst[ny][nx] = true;
                sum += cnt + 1;
                map[ny][nx] = 0;
                cnt = 0;
                while(!q.empty()) q.pop(); //큐 리셋
                q.push({{ny, nx}, cnt});
                fishcnt += 1;
                if(fishcnt == size) {
                    fishcnt = 0;
                    size++;
                }
                break;
            }
            //Passable or zero
            else if(map[ny][nx] == size || map[ny][nx] == 0) {
                if(vst[ny][nx]) continue;
                vst[ny][nx] = true;
                q.push({{ny, nx}, cnt + 1});
            }
        }
    }
    cout << sum;
}