[C/C++] 백준 16236: 아기 상어 (BFS, 반례 및 주의점!)

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

16236 아기상어 입력

 

 

사실 BFS로 돌면서 풀면되는 아주 간단한 문제인줄 알았지만 생각보다 해야할게 많아서 굉장히 고민을 많이 했다. 무려 3시간만에 겨우 풀었다... 문제 해설보다는 내가 실수했던 부분 위주로 한번 써보려고 한다.

 

주의해야할 점!

1. 지나가는 것과 먹을 수 있는 경우

 문제에 그대로 나와있다싶이 자신의 크기보다 큰 물고기가 있는 칸을 제외한 칸은 모두 지나갈 수 있고 자신의 크기보다 작은 물고기만 먹을 수 있다. 이때 주의해야 할 점은 자신의 크기와 같은 물고기인데, 이때는 지나갈 수는 있고 먹을 수는 없다! 따라서 코드를 작성할 때 이 부분을 분리해서 적어줘야 한다.

 

2. 먹을 수 있는 물고기가 1마리보다 많을 때

 사실 이 부분에서 가장 많이 실수를 하고 나도 여기서 많이 해맸는데...

이 말을 뜻을 잘 이해해야한다. 이게 거리가 똑같이 가까운 물고기들 중에 가장 위에 있는 물고기를 우선 순위로, 가장 위에 있는 물고기도 여러개라면 가장 왼쪽에 있는 물고기를 먹는다는 것이다. 이게 무슨 말이냐면 다른 BFS 탐색 문제처럼 위,왼쪽,오른쪽,아래 순으로 탐색을 한 뒤에 가장 먼저 도달한 지점이 답이 되는 것이 아니다. 틀린 방법대로 구현을 할 경우에 4%에서 틀렸습니다가 뜨고 예제 입력 4의 답이 60이 아니라 56이 나올 것이다!

 

 그래서 이것을 구현하는 방법은 BFS로 돌다가 같은 거리에 있는 좌표들을 모두 이차원 백터로 저장한 뒤에 sort 함수를 이용하여 정렬하여 가장 위에 있으면서 왼쪽에 있는 좌표를 탐색해야 한다. Map으로도 구현이 가능하지만 map은 key 값만으로 정렬을 하기 때문에 value 값은 오름차순으로 정렬이 되지 않는다. 이럴 경우

 

7
2 0 6 1 2 4 1
2 0 0 0 1 6 1
3 5 1 0 2 5 0
3 0 0 9 1 0 4
6 1 1 0 2 1 6
0 0 4 0 4 1 2
5 0 0 0 4 0 2 

 

의 값이 59로 나오지 않을 것이다. 

 

3.  아기 상어의 초기 위치 

 아기 상어의 초기 위치가 9로 되어있는데 이것을 0으로 바꿔줘야한다. 일단 구현할 때도 조건문 쓰기가 복잡해지고 무엇보다 아기상어의 몸집이 9보다 커질 수도 있어 초기 위치가 먹이라고 생각할 수도 있기 때문이다. 

 

4. queue와 tuple

 queue에 x좌표, y좌표, 그리고 현재까지의 거리를 구해야만 그 다음에 queue를 꺼내서 연산을 할 때 거리를 정확하고 쉽게 계산할 수 있다.  tuple의 선언은

queue<tuple<int,int,int>> q1;

 

각 값을 꺼낼 때는 

 nx=get<0>(q1.front())+x_coordinate[i];
 ny=get<1>(q1.front())+y_coordinate[i];
 distance=get<2>(q1.front())+1;

이런 식으로 get을 이용해 꺼내준다.

 

소스코드!

 

#include <iostream>
#include <algorithm>
#include<queue>
#include<tuple>
#include <string.h>
#include <map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

vector <pair<int,int>> v1;
int k=100000000;
int graph[21][21];
int fish[7];
int x_coordinate[4]={0,-1,1,0};  
int y_coordinate[4]={-1,0,0,1}; 
queue<tuple<int,int,int>> q1;

int visit_once[21][21];
int n;
int distanceS=0;
void TravelForEat(int x, int y,int shark_size,int WantBig);

void bfs(int x,int y,int shark_size,int WantBig){  
  q1.push(make_tuple(x,y,distanceS));
  visit_once[y][x]=1;
  while(q1.size()!=0){ //
    int nx,ny,distance=get<2>(q1.front())+1;;
    if(k==distance-1) //중복되는 것 중에 가장 위, 그 다음에 가장 왼쪽에 있는 걸 찾으려고 함!
    {
      int tmpx,tmpy;
      sort(v1.begin(),v1.end());
      tmpy=v1.begin()->first;      
      tmpx=v1.begin()->second;      
      memset(visit_once,0,21*21*sizeof(int));
      q1=queue<tuple<int,int,int>>(); //queue초기화
      fish[graph[tmpy][tmpx]]--; //물고기 숫자 바꿔줌        
      distanceS=distance-1; //지나간 시간 더해줌
      graph[tmpy][tmpx]=0; //지나간 자리를 0으로 만들어줌(굳이 할 필요는 없음)
      k=1000000;
      v1.clear();     
      
      TravelForEat(tmpx,tmpy,shark_size,++WantBig);
      return;
    }
    
  for(int i=0;i<4;i++) //BFS를 queue를 이용하여 구현
    {
      nx=get<0>(q1.front())+x_coordinate[i];
      ny=get<1>(q1.front())+y_coordinate[i];
      distance=get<2>(q1.front())+1; //현재까지의 거리      

      if(nx<1 ||nx>n ||ny<1 ||ny>n) //graph 범위에서 벗어남
        continue;      
      if(graph[ny][nx]>shark_size  ||visit_once[ny][nx]==1) // 상어가 지나갈 수 없는 곳/ 이미 지나간 곳
        continue;
      
      visit_once[ny][nx]=1;    
      if(graph[ny][nx]>0 && graph[ny][nx]<shark_size) //먹을 수 있는물고기가 있다!, 일단 백터의 저장
      {
        v1.push_back(make_pair(ny,nx));        
        k=distance;
      }      
      //0인 곳을 지날 때 혹은 같은 무게
      q1.push(make_tuple(nx,ny,distance));      
    }
  q1.pop();    
  }
  
}

void TravelForEat(int x, int y,int shark_size,int WantBig)
{
  if(WantBig==shark_size) //상어 크기 커짐
  {
    shark_size++;
    WantBig=0;
  }
  int go_result=0;
  for(int i=1;i<=shark_size-1;i++) // 더 이상 먹을게 없을 때
    {
      if(fish[i]!=0){
        go_result=1;
        break;
      }        
    }
  if(go_result==0) //먹을게 없으면 엄마 상어를 불러!
    return;
  bfs(x,y,shark_size,WantBig);  
  return;
}


int main() {
  int tmp,y_shark,x_shark,shark_size=2;
  cin>>n;
  for(int j=1;j<=n;j++) //graph저장 및 물고기 개수 저장
    {
      for(int i=1;i<=n;i++)
        {
          cin>>tmp;
          graph[j][i]=tmp;
          if(tmp!=0){
            if(tmp==9){
              y_shark=j;
              x_shark=i;
              graph[j][i]=0; //어차피 여기도 나중에는 빈공간이 될거임
            }
            else
              fish[tmp]++;
          }    
        }
    }
  TravelForEat(x_shark,y_shark,shark_size,0);
  cout<<distanceS;
}