[백준] C++ 16236(아기 상어)

#include <iostream>
#include <queue>
#define INF 987654321

using namespace std;

int arr[21][21];

void BFS(int SL, int SC);

int N=0;

int main(void)
{
	cin>>N;
	
	int SL=0;
	int SC=0;
	
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			cin>>arr[i][j];
			if(arr[i][j]==9)
			{
				SL=i;
				SC=j;
				arr[i][j]=0;
			}
		}
	}
	
	BFS(SL,SC);
	
	return 0;
}

void BFS(int SL, int SC)
{
	queue<pair<int,int> > Q;
	queue<int> Q2;
	Q.push(make_pair(SL,SC));
	Q2.push(0);
	
	int level=2;
	int eat=0;
	
	int visited[21][21]={0};
	
	int sum=0;
	
	int Mindistance=INF;
	int Mini=INF;
	int Minj=INF;
	
	while(!Q.empty())
	{
		int i=Q.front().first;
		int j=Q.front().second;
		Q.pop();
		int distance=Q2.front();
		Q2.pop();
		
		visited[i][j]=1;
		
		if(arr[i][j]>0&&arr[i][j]<level)//먹을 수 있다면?? 
		{
			if(Mindistance>=distance)//가장 가깝고 가장 위에 있는 먹이감의 위치를 저장 
			{
				Mindistance=distance;
				if(i<Mini)//위에 있는 먹이 우선 
				{
					Mini=i;
					Minj=j;
				}
				else if(i==Mini)//왼쪽에 있는 먹이 우선 
				{
					if(j<Minj)
					{
						Minj=j;
					}
				} 
			}
		}
		else//상 하 좌 우 이동 
		{
			if(visited[i-1][j]==0&&arr[i-1][j]<=level&&i-1>-1)
			{
				visited[i-1][j]=1;
				Q.push(make_pair(i-1,j));
				Q2.push(distance+1);
			}
			
			if(visited[i+1][j]==0&&arr[i+1][j]<=level&&i+1<N)
			{
				visited[i+1][j]=1;
				Q.push(make_pair(i+1,j));
				Q2.push(distance+1);
			}
			
			if(visited[i][j-1]==0&&arr[i][j-1]<=level&&j-1>-1)
			{
				visited[i][j-1]=1;
				Q.push(make_pair(i,j-1));
				Q2.push(distance+1);
			}
			
			if(visited[i][j+1]==0&&arr[i][j+1]<=level&&j+1<N)
			{
				visited[i][j+1]=1;
				Q.push(make_pair(i,j+1));
				Q2.push(distance+1);
			}
			
			
			
		}
		
		if(Q.empty())//모든 위치를 확인 했다면?? 
		{
			if(Mindistance!=INF)
			{
				eat++;
				arr[Mini][Minj]=0;
				sum=sum+Mindistance;
				for(int l=0; l<21; l++)
				{
					for(int k=0; k<21; k++)
					{
						visited[l][k]=0;
					}
				}
				
				Q.push(make_pair(Mini,Minj));//먹은 위치 다시 삽입 
				Q2.push(0);
				
				Mindistance=INF;//초기화 
				Mini=INF;
				Minj=INF;
				
				if(eat==level)
				{
					level++;
					eat=0;
				}
			}
		}
	}
	
	cout<<sum;
	
}

아기상어가 물고기를 잡아먹을 수 있는 시간을 출력하는 문제이다.

 

조건

• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
• 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야 하는 칸의 개수의 최솟값이다.
• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

제일 가까운 물고기를 잡아먹으면서 먹을 수 있는 물고기가 먹을 때까지 이동해야 한다. 만약 동일한 거리에 물고기가 여러 마리가 존재할 경우

 

위에 있는 물고기를 우선적으로 먹고, 만약 높이가 같은 경우 왼쪽에 있는 물고기를 우선적으로 먹는다.

 

이 문제에서 핵심은 우선적으로 먹을 물고기를 정하는 것이다.

어떻게 하면 상 하 좌 우를 비교하여 우선적으로 먹을 물고기를 정할 수 있을까??

 

나는 상어가 현재 위치에서 갈 수 있는 모든 곳을 돌아보도록 하였다. 그러고 상어가 먹을 수 있는 가장 가까운 물고기의 위치를 저장한다.(높은 곳 우선, 왼쪽 우선)

 

if(arr[i][j]>0&&arr[i][j]<level)//먹을 수 있다면?? 
		{
			if(Mindistance>=distance)//가장 가깝고 가장 위에 있는 먹이감의 위치를 저장 
			{
				Mindistance=distance;
				if(i<Mini)//위에 있는 먹이 우선 
				{
					Mini=i;
					Minj=j;
				}
				else if(i==Mini)//왼쪽에 있는 먹이 우선 
				{
					if(j<Minj)
					{
						Minj=j;
					}
				} 
			}
		}

 

만약 큐가 비면??(모든 위치를 확인했다면?)

가장 가까운 물고기를 먹는다!(만약 먹을 게 없다면 그대로 while문을 빠져나온다.)

if(Q.empty())//모든 위치를 확인 했다면?? 
		{
			if(Mindistance!=INF)
			{
				eat++;
				arr[Mini][Minj]=0;
				sum=sum+Mindistance;
				for(int l=0; l<21; l++)
				{
					for(int k=0; k<21; k++)
					{
						visited[l][k]=0;
					}
				}
				
				Q.push(make_pair(Mini,Minj));//먹은 위치 다시 삽입 
				Q2.push(0);
				
				Mindistance=INF;//초기화 
				Mini=INF;
				Minj=INF;
				
				if(eat==level)
				{
					level++;
					eat=0;
				}
			}
		}

왼쪽에 있는 물고기가 오른쪽에 있는 물고기보다 밑에 있는데 왼쪽 물고기를 먼저 먹게 될 수도 있으니 이 부분을 주의해서 문제를 풀어야 한다.

 

상어가 현재 위치에서 *모든 곳*을 확인한 후 가장 가까운 물고기를 찾아가는 것이 핵심 포인트다.