[16236] 아기 상어 - C++

---

풀이

이번 글에서는 어떻게 구상하고 설계했는지 자세하게 적어 보려고 한다

 

1. 나에게 가까운 것을 찾아야 한다.

BFS를 사용할 수 있을 듯하다.

가까운 것이 여러 개 있다면 가장 위에 있는 것, 그중에서도 여러 개 있다면 가장 왼쪽의 것을 고르라 하니 

BFS를 돌고 for문을 사용해도 될 듯하다.

 

시간을 표시해줘야 하니 Dist라는 -1로 채워진 $ N \times N $ 배열을 만들어 줘야 한다.

 

2. 상어를 성장시켜야 한다.

baby라는 상어의 현재 크기를 담는 변수

growing이라는초기값은 0이고, 물고기를 먹을 때마다 증가시킨다.

 

만약 baby 변수와 값이 동일해진다면 baby증가, growing은 0으로 초기화

즉 상어의 무게를 늘려주는 식으로 구상했다.

 

3. 종료 조건

무한 반복을 돌리며 더 이상 상어가 이동할 곳이 없을 때 시간을 출력하고 return 하는 식으로 구상함

---

코드

#include <bits/stdc++.h>

//불가능한 값 Max
#define Max 1000

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, t = 0;

int board[22][22], dist[22][22];

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

queue<tuple<int, int, int>> q;

int baby = 2;
int growing = 0;

bool OOB(int nx, int ny){
  return nx < 0 || nx >= n || ny < 0 || ny >= n;
}

void distInit(int size){
  for(int i = 0; i < size; ++i)
    fill(dist[i], dist[i] + size, -1);
}

int main(){
  init();
  cin >> n;
  
  //dist를 -1로 초기화하는 함수
  distInit(n);
  
  //입력
  for(int i= 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      cin >> board[i][j];
      if(board[i][j] == 9){
      	//입력 받으며 시작 위치를 찾아냄
        q.push({i, j, 0});
        
        //시작부분의 시간은 0으로 변경
        dist[i][j] = 0;
      }
    }
  }

  while(1){
  	//BFS
    while(!q.empty()){
      int x, y, cnt; tie(x, y, cnt) = q.front(); q.pop();
      
      int nxtCnt = cnt + 1;
      for(int dir = 0; dir < 4; ++dir){
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if(OOB(nx, ny)) continue;
        if(dist[nx][ny] > -1 || board[nx][ny] > baby)continue;

        q.push({nx, ny, nxtCnt});
        //나와 동일한 크기의 물고기라면 불가능한 크기의 값으로 바꿔주고
        //나보다 작다면 nxtCnt를 넣어준다.
        dist[nx][ny] = (board[nx][ny] == baby ? Max : nxtCnt);
      }
    }
    
    //불가능한 값  MAX를 mins의 초기값으로 넣어준다.
    int mins = Max;
    
    //먹은 물고기의 위치를 넣어줄 변수 x, y
    int x, y;
    for(int i= 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        //전 시작위치 9는 0으로 바꿔준다.
        if(board[i][j] == 9) board[i][j] = 0;
        else if(board[i][j] > 0 && dist[i][j] != -1 && mins > dist[i][j]){
          mins = dist[i][j];
          x = i; y = j;
        }
      }
    }

	// mins가 변경 되었다면, 즉 물고기를 하나라도 먹었다면 실행
    if(mins != Max){
      t += dist[x][y];
      board[x][y] = 9;
      q.push({x, y, 0});
      if(++growing == baby){baby++;growing = 0;}
      distInit(n);
      dist[x][y] = 0;
    } else{
      cout << t << '\n';
      return 0;
    }
  }
  return 0;
}

---

글을 마치며

오랜만에 구현 && BFS 문제를 풀어 보았는데 예전보다 성장한 게 눈에 보여서 좋다.

처음 구현 문제를 풀 때는 어떻게 풀지 몰라 당황하고 그랬었는데, 많이 풀고 익숙해지니 늘긴 하는구나

근데 코드가 너무 더러운 것 같은데 이건 어떻게 해결해야 하지