[백준][BFS] 16236번 아기상어

문제

아기 상어와 물고기들이 존재하는 공간이 주어지고, 아기 상어는 물고기를 먹으며 크기를 증가시키는데 조건에 맞춰서 먹을 수 있는 물고기가 있고 커지는 조건이 있다. 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하는 문제이다.

출처: 백준 온라인 저지 https://www.acmicpc.net/problem/16236

풀이

아무리 풀어봤더라도 잘 이해하고 넘어갔는지가 중요한 거니까 오랜만에 풀이를 남긴다. 이 문제 처음에 봤을 때는 당황스러웠다. 꽤 복잡해 보였고, 이렇게 풀어도 되나? 하는 몇 가지 방법만 떠올랐는데 그 방법을 정리해서 푸니 풀렸다. 우선 아기 상어는 처음 크기가 2이고, 자신보다 작은 크기의 물고기만 먹을 수 있다. 그리고 자신의 크기와 동일한 수만큼 물고기를 먹으면 크기가 1이 커진다. 물고기를 잡아먹을 때는 자신에게 가장 가까운 물고기를 먹어야 하는데 만약 같은 최단 거리에 물고기가 여러 마리라면 가장 위쪽, 그것도 동일하다면 가장 왼쪽의 물고기를 먹도록 한다. 그리고 자신보다 큰 물고기가 있으면 그 자리를 못 지나가기 때문에 BFS를 써서 탐색해야 했다.(장애물이 없었다면 절대값으로 구할 수 있었을 텐데..) BFS를 통해 1초씩 늘리며 갈 수 있는 좌표를 탐색하고 만약 잡아먹을 수 있는 물고기가 탐색되면 그 해당하는 초에 탐색할 수 있는 부분을 다 탐색하고, 우선순위 큐에서 가장 위쪽에 있거나 가장 왼쪽에 있는 물고기의 좌표를 꺼내서 해당 물고기를 잡아먹고 거기를 다시 시작하는 지점으로 바꾸고, 1초씩 늘려가며 BFS를 통해 마찬가지로 탐색한다. BFS를 위한 전체 조건은 이동할 수 있는 좌표가 있을 때까지 이므로 더이상 갈 곳이 없으면 잡아먹을 수 있는 물고기가 없으므로 종료된다. visited 배열을 통해서 한번 갔던 좌표는 안 가게 해주려 했는데 한번 잡아먹고 나면 새로운 탐색이므로 초기화를 해줘야 했다. 어느 부분에서 초기화를 해야 하는지 조금 헷갈렸었다.

코드

void init()

{

for(int i=0; i<N; i++)

for(int j=0; j<N; j++)

visit[i][j]=0;

}

struct cmp{

   bool operator()(const pair<int, int> a, const pair<int, int> b){

      if(a.first == b.first){

  return a.second > b.second;

      }

      return a.first > b.first;

   }

};

int BFS(){

int cnt=0;

int time=0;

int fish_size=2;

int result = 0;

queue<pair<int, int>> step;

priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> eat_fish;

step.push(make_pair(x, y));

visit[x][y] = 1;

map[x][y]=0;

pair<int, int> curr;

int size;

while(!step.empty())

{

size = step.size();

for(int i=0; i<size; i++){

curr = step.front();

step.pop();

x = curr.first;

y = curr.second;

if(map[x][y] != 0 &&

map[x][y] < fish_size){

eat_fish.push(make_pair(x, y)); 

//먹을 수 있는 먹이가 존재할 때 QUEUE에 넣어서 같은 거리에 물고기를 우선순위를 비교하려고

}

for(int j=0; j<4; j++){

if(x+dx[j] < 0 || x+dx[j] >= N ||

y+dy[j] < 0 || y+dy[j] >= N)

continue;

if(visit[x+dx[j]][y+dy[j]] == 0

&& map[x+dx[j]][y+dy[j]] <= fish_size ){

visit[x+dx[j]][y+dy[j]] = 1;

step.push(make_pair(x+dx[j], y+dy[j]));

}

}

}

if(eat_fish.size() != 0){ //먹을 수 있는 먹이가 있다는 뜻

map[eat_fish.top().first][eat_fish.top().second] = 0; //top()에 있는 먹기 = 가장 위쪽이거나 가장 왼쪽인 경우! 위의 cmp로 처리

cnt++; 

if(fish_size == cnt){

fish_size++;

cnt=0;

}

curr.first = eat_fish.top().first;

curr.second = eat_fish.top().second;

while(!step.empty())

step.pop();

while(!eat_fish.empty())

eat_fish.pop();

step.push(curr);

result += time;

time = 0;

init();

}

else

time++;

}

return result;

}