BOJ 16236, 아기상어

Source: BOJ 16236 아기상어

생각보다 애를 먹은 문제였다.

처음에 문제를 잘 못 이해하여 bfs방향 (위, 왼쪽, 오른쪽, 아래) 으로 탐색하면 문제에 맞는 물고기를 선택할 수 있을 줄 알았는데, 아니었다..!
다시 차근차근 고민해보아서 상어가 잡을 수 있는 물고기를 bfs로 찾은후 그 물고기를 다시 vector에 push_back 하고, sort함수를 이용해 거리가 가장 가까우면서 위, 왼쪽 순으로 정렬된 물고기 중 첫번째 물고기를 잡아먹도록 수정하였다.

---

알고리즘 논리전개

1. 주어진 board안에 먹을 수 있는 물고기를 찾음.
2. 찾은 물고기가 없으면 return, 있으면 물고기를 vector<dist, row, col>에 push_back
3. 물고기를 넣은 vector를 sort함수로 거리, 행, 열 순으로 정렬
4. 정렬된 vector의 첫번째 물고기 자리로 상어가 이동

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
int n;
int board[21][21];
int dist[21][21];
int shark_size = 2;
int cnt;
int ans;

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>n;
  int shark_x, shark_y;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>>board[i][j];
      if(board[i][j] == 9){
        shark_x = i;
        shark_y = j;
      }
    }
  }
  bool flag = false;
  while(1){
    vector<tuple<int, int, int>> v;
    for(int i=0; i<n; i++){
      fill(dist[i], dist[i]+n, -1);
    }
    if(flag) break;
    dist[shark_x][shark_y] = 0;
    queue<pair<int, int>> Q;
    Q.push({shark_x, shark_y});
    board[shark_x][shark_y] = 0;
    while(!Q.empty()){
      flag = true;
      auto cur = Q.front(); Q.pop();
      for(int i=0; i<4; i++){
        int nx = cur.X + dx[i];
        int ny = cur.Y + dy[i];
        if(nx<0||ny<0||nx>=n||ny>=n) continue;
        if(dist[nx][ny] !=-1 || board[nx][ny] > shark_size) continue;
        dist[nx][ny] = dist[cur.X][cur.Y]+1;
        Q.push({nx, ny});
        if(board[nx][ny] !=0 && board[nx][ny] < shark_size) {
          v.push_back({dist[nx][ny], nx, ny});
        }
      }
    }
    if(!v.empty()){
      sort(v.begin(), v.end());
      ans+= get<0>(v[0]);
      board[get<1>(v[0])][get<2>(v[0])] = 0;
      cnt++;
      if(cnt == shark_size) {shark_size++; cnt = 0;}
      shark_x = get<1>(v[0]);
      shark_y = get<2>(v[0]);
      flag = false;
    }
  }
  cout<<ans;
}