[백준 16236] 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

bfs를 사용하는 구현문제. 조건이 너무 많다.

 

1. 물고기가 있는 지 확인

2. 있다면 먹기

3. 여러 마리라면 우선순위가 있다. 가까운 물고기 -> 위쪽 ->  왼쪽 에 있는 물고기 먹기

4. 없으면 엄마 상어 부르기

이다.

 

물고기를 먹기 위한 조건은 크기보다 작은 경우에만 가능하다. 

크기가 동일하면 지나가는 것만 가능

 

크기가 커지는 조건은 물고기를 크기만큼 먹었을 때 크기가 1만큼 커진다.

 

1 2 3 4 를 확인하기 위해 bfs를 사용한다.

path 배열로 물고기까지 도달할 때 시간을 체크하고 가까운 + 위쪽 + 왼쪽을 확인하여 물고기 위치를 저장하고 while문이 끝나면 마지막에 저장된 물고기 위치에 있는 물고기를 먹는다.

 

물고기를 먹으면 먹은 물고기 수를 업데이트하고 arr배열의 해당 위치에 0을 집어넣는다.

 

#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;

int n;
int arr[20][20];
int path[20][20];
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, -1, 0, 1};

int time, status = 2;
int sr, sc;
int fish;
int mr, mc, md = 500;

struct Shark
{
  int row, col;
};

void bfs()
{
  queue<Shark> q;
  memset(path, -1, sizeof(path));
  q.push({sr, sc});
  path[sr][sc] = 0;

  while (!q.empty())
  {
    Shark cur = q.front();
    q.pop();

    for (int i = 0; i < 4; i++)
    {
      int nr = cur.row + dr[i];
      int nc = cur.col + dc[i];

      if (nr > -1 && nr < n && nc < n && nc > -1 &&
          path[nr][nc] == -1 && arr[nr][nc] <= status)
      {
        path[nr][nc] = path[cur.row][cur.col] + 1;
        q.push({nr, nc});

        if (arr[nr][nc] < status && arr[nr][nc] > 0)
        {
          if (md > path[nr][nc])
          {
            md = path[nr][nc];
            mr = nr;
            mc = nc;
          }
          else if (md == path[nr][nc])
          {
            if (mr == nr && mc > nc)
            {
              mr = nr;
              mc = nc;
            }
            else if (mr > nr)
            {
              mr = nr;
              mc = nc;
            }
          }
        }
      }
    }
  }

  if (md < 500)
  {
    time += md;
    arr[mr][mc] = 0;
    fish++;
    if (fish == status)
    {
      status++;
      fish = 0;
    }
    sr = mr, sc = mc;
  }

}
int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      scanf("%d", &arr[i][j]);
      if (arr[i][j] == 9)
      {
        sr = i;
        sc = j;
        arr[i][j] = 0;
      }
    }
  }

  while (1)
  {
    md = 500;
    bfs();
    if (md == 500)
    {
      printf("%d\n", time);
      return 0;
    }
  }
  return 0;
}