[백준] 16236번 아기 상어

16236번 아기 상어

---

1. 이해하기

• 가장 처음에 아기 상어의 크기는 2이고, 1초에 상하좌우로 인접한 한 칸씩 이동할 수 있다.
• 아기 상어는 자산의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다.
• 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 크기가 같은 물고기는 먹을 수 없지만 지나갈 수는 있다.
• 아기 상어가 어디로 이동할지 결정하는 방법
  • 더 이상 먹을 수 있는 물고기가 없을 때 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야 하는 칸의 개수의 최솟값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
• 아기 상어가 물고기를 먹는데 걸리는 시간은 없다. 먹으면 그 칸은 빈칸이 된다.
• 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다.
• 아기 상어가 엄마 상어의 도움을 바랄 때의 시간을 구하는 문제.

---

2. 구현하기

• 물고기가 각 물고기를 먹으러 가는데 걸리는 거리를 bfs를 이용하여 구한다.

  void bfs(Shark shark) {
      memset(dist,-1,sizeof(dist));
      queue<Point> q;
      q.push({shark.p.x,shark.p.y});
      dist[shark.p.x][shark.p.y] = 0;
      while(!q.empty()) {
          int x = q.front().x, y = q.front().y; q.pop();
          for(int i = 0; i < 4; i++) {
              int nx = x+dx[i], ny = y+dy[i];
              if(nx < 0 or nx >= N or ny < 0 or ny >= N) continue;
              if(dist[nx][ny] != -1) continue;
              if(map[nx][ny] > shark.size) continue;
              q.push({nx,ny});
              dist[nx][ny] = dist[x][y]+1;
          }
      }
  }

• 거리를 구한 것을 바탕으로 아기 상어가 위치할 다음 좌표를 구한다.

  Point get_next_location(Shark shark) {
      bfs(shark);
      Point next = {-1,-1};
      int min_dist = -1;
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < N; j++) {
              if(1 <= map[i][j] and map[i][j] <= 6 and dist[i][j] != -1) {
                  if(shark.size <= map[i][j]) continue;
                  if(min_dist == -1 || dist[i][j] < min_dist)  {
                      next = {i,j}; min_dist = dist[i][j];
                  }
              }
          }
      }
      return next;
  }

• 먹을 물고기가 없을 때까지 반복한다.

  int simulate(Shark shark) {
      int time = 0;
      while(1) {
          Point next = get_next_location(shark);
          if(next.x == -1) break;
          time += dist[next.x][next.y];
          map[next.x][next.y] = 0;
          shark.p = next; shark.cnt++;
          if(shark.cnt == shark.size) {
              shark.cnt = 0; shark.size++;
          }
      }
      return time;
  }

---

3. 전체 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct Point {
    int x,y;
};
struct Shark {
    Point p;
    int size,cnt;
};
int map[20][20];
int dist[20][20];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N;

void bfs(Shark shark) {
    memset(dist,-1,sizeof(dist));
    queue<Point> q;
    q.push({shark.p.x,shark.p.y});
    dist[shark.p.x][shark.p.y] = 0;
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if(nx < 0 or nx >= N or ny < 0 or ny >= N) continue;
            if(dist[nx][ny] != -1) continue;
            if(map[nx][ny] > shark.size) continue;
            q.push({nx,ny});
            dist[nx][ny] = dist[x][y]+1;
        }
    }
}

Point get_next_location(Shark shark) {
    bfs(shark);
    Point next = {-1,-1};
    int min_dist = -1;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(1 <= map[i][j] and map[i][j] <= 6 and dist[i][j] != -1) {
                if(shark.size <= map[i][j]) continue;
                if(min_dist == -1 || dist[i][j] < min_dist)  {
                    next = {i,j}; min_dist = dist[i][j];
                }
            }
        }
    }
    return next;
}

int simulate(Shark shark) {
    int time = 0;
    while(1) {
        Point next = get_next_location(shark);
        if(next.x == -1) break;
        time += dist[next.x][next.y];
        map[next.x][next.y] = 0;
        shark.p = next; shark.cnt++;
        if(shark.cnt == shark.size) {
            shark.cnt = 0; shark.size++;
        }
    }
    return time;
}

void input(Shark& shark) {
    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) {
                shark = {{i,j},2,0};
                map[i][j] = 0;
            }
        }
    }
}

int main() {
    Shark shark;
    input(shark);
    cout << simulate(shark) << '\n';
    return 0;
}