[16236] 아기 상어

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

16236번: 아기 상어

<문제>

탐색의 방법이 정형화된 bfs이고, 기준도 부등식 하나로 매우 간단하다.

주의할 점으로는, 초기에 아기상어가 위치한 곳에도 0(빈칸)으로 표시를 해두어야 한다.

queue에 넣는것은 매칸마다 이동하는 것이 아닌,

아기상어가 하나의 물고기를 잡아먹을때마다 하나의 정점을 방문하는 것으로 생각한다.

<소스코드>

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
const int INF = 12345;
int n, a[21][21], dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 }, dist[21][21];
queue <pair<int, int>>q;
vector < pair<int, pair<int, int>> >v;
int targetY, targetX, targetDist;
void f(int sy, int sx, int level) {
    int i, j, ty, tx, y, x;
    memset(dist, 0, sizeof(dist));
    while (!q.empty())q.pop();
    q.push({ sy,sx });
    targetY = targetX = targetDist = INF;
    while (!q.empty()) {
        ty = q.front().first;
        tx = q.front().second;
        q.pop();
        for (i = 0; i < 4; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (y < 0 || x<0 || y >= n || x >= n || a[y][x] > level || dist[y][x]>0)continue;
            dist[y][x] = dist[ty][tx] + 1;
            if (a[y][x] == 0 || a[y][x] == level)q.push({ y,x });
            if (a[y][x] < level && a[y][x] != 0) {
                if (dist[y][x] < targetDist) {
                    targetY = y;
                    targetX = x;
                    targetDist = dist[y][x];
                }
                else if (dist[y][x] == targetDist) {
                    if (y < targetY) {
                        targetY = y;
                        targetX = x;
                        targetDist = dist[y][x];
                    }
                    else if (y == targetY && x < targetX) {
                        targetY = y;
                        targetX = x;
                        targetDist = dist[y][x];
                    }
                }
            }
        }
    }
}
int main(void) {
    int i, j, startY = 0, startX = 0, cnt = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] != 0 && a[i][j] != 9)cnt++;
            if (a[i][j] == 9) {//상어가 있을때
                a[i][j] = 0;//물고기는 없는것으로 표시
                startY = i;
                startX = j;
            }
        }
    }
    int level = 2, nextLevel = 2, turn = 0;
    for (i = 0; i < cnt; i++) {
        f(startY, startX, level);
        if (targetY < 0 || targetY >= n || targetX < 0 || targetX >= n) {
            break;
        }
        a[targetY][targetX] = 0;
        turn += targetDist;
        if (nextLevel == 1) {
            nextLevel = level + 1;
            level++;
        }
        else {
            nextLevel--;
        }
        startY = targetY;
        startX = targetX;
    }
    printf("%d", turn);
    return 0;
}