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

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

16236번: 아기 상어

 본 문제는 삼성 SW 역량 테스트 기출 문제로 크기가 2인 아기 상어가 1초에 상하좌우로 인접한 한 칸씩 이동하면서 물고기를 먹는 문제다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있고, 크기가 같은 물고기는 지나갈 수 있다. 이동결정 방법에 조건이 있는데

1. 더 이상 먹을 수 있는 물고기가 없다면 끝.
2. 먹을 수 있는 물고기가 1마리면, 그 물고기를 먹는다.
3. 먹을 수 있는 물고기가 1마리보다 많으면, 거리가 가장 가까운 물고기를 먹는다.
   1. 거리는 지나야하는 칸의 개수의 최소값이다.
   2. 거리가 가까운 물고기가 많다면, (1) 가장 위에 있는 물고기 (2) 가장 왼쪽에 있는 물고기

의 조건이 있다.

해결 방법은

1. 현재 아기상어의 위치에서 먹을 수 있는 물고기 탐색
2. 물고기들 거리, 위, 왼쪽 순으로 정렬
3. 먹으러 간다.

#include <cstdio>
#include <queue>
#include <tuple>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
bool cmp(tuple<int, int, int> v, tuple<int, int, int> u) {
    int vx, vy, vcnt;
    int ux, uy, ucnt;
    tie(vx, vy, vcnt) = v;
    tie(ux, uy, ucnt) = u;
    if (vcnt == ucnt) {
        if (vx == ux) {
            // 가장 위에
            return vy < uy;
        }
        // 가장 왼쪽
        else return vx < ux;
    }
    // 거리 순
    else return vcnt < ucnt;
}
 
int d[22][22];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, sx, sy;
int shark = 2, eat = 0, ans = 0;
bool chk[22][22];
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &d[i][j]);
            if (d[i][j] == 9) {
                sx = i;
                sy = j;
                d[i][j] = 0;
            }
        }
    }
    queue<tuple<int, int, int>> q;
    q.push(make_tuple(sx, sy, 0));
    chk[sx][sy] = true;
    
    vector<tuple<int, int, int>> v;
    while (true) {
        while (!q.empty()) {
            int x, y, cnt;
            tie(x, y, cnt) = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (!chk[nx][ny]) {
                        if (d[nx][ny] > shark) continue;
                        // 먹을 수 있는 물고기 탐색
                        else if (d[nx][ny] != 0 && d[nx][ny] < shark){
                            chk[nx][ny] = true;
                            q.push(make_tuple(nx, ny, cnt+1));
                            v.push_back(make_tuple(nx, ny, cnt+1));
                        }
                        else {
                            chk[nx][ny] = true;
                            q.push(make_tuple(nx, ny, cnt+1));
                        }
                    }
                }
            }
        }
        // 더 이상 먹을 수 잇는 물고기가 없을 때
        if (v.size() == 0) {
            printf("%d\n", ans);
            return 0;
        }
        // 먹을 수 있는 물고기 정렬
        sort(v.begin(), v.end(), cmp);
        int a, b, c;
        tie(a, b, c) = v.front();
        eat += 1;
        ans += c;
        d[a][b] = 0;
        memset(chk, false, sizeof(chk));
        chk[a][b] = true;
        q.push(make_tuple(a, b, 0));
        v.clear();
        if (eat == shark) {
            shark += 1;
            eat = 0;
        }
    }
}