백준 16236번: 아기 상어 (C++)

문제 링크 : https://www.acmicpc.net/problem/16236

 

 

bfs문제입니다.

 

<전체적인 알고리즘>

  bfs로 먹을 수 있는 먹이를 계속 찾습니다. bfs가 끝날때 마다 먹이를 찾는데 걸리는 시간을 계속 더해줍니다. 

  만약 먹을 수 있는 먹이가 더이상 없다면 종료시켜줍니다.

 

<부연 설명>

  -  최단 거리의 먹이들 중 가장 위쪽에서 왼쪽인 먹이를 찾기위해 일단 최단 거리의 먹이를 전부 저장해야함

         -> 처음 먹이를 찾을때의 거리(최단 거리)를 저장한 후 거리가 더 커지기 전까지의 먹이를 전부 저장한다.

              (bfs는 가까운 것부터 탐색하므로 거리가 같은 부분끼리 뭉쳐서 queue에 저장된다.)

 

<자료 구조>

  - 상어 정보를 저장하는 class (저장해야 하는 속성이 3개 이상이라 class를 정의함)

  - 같은 거리의 먹이들을 임시저장하기위한 vector

  

 

 

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int map[22][22];
int baby_x, baby_y;    //아기상어 위치
int baby_size=2;       //아기상어 크기
int baby_prey = 2;     // 진화하려면 먹어야 하는 먹이 개수
bool check[22][22];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int n;

class ins
{
public:
	int x, y, count;
	ins(int x, int y, int count)
	{
		this->x = x;
		this->y = y;
		this->count = count;
	}
};

int bfs(int startx, int starty)
{
	queue<ins> q;
	vector < pair<int, int>> v;
	fill(&check[0][0], &check[19][20], 0);
	q.push(ins(startx, starty, 0));
	check[startx][starty] = true;

	int result_count = -1;
	
	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		int count = q.front().count;   //거리
		q.pop();

		if (map[x][y]>0&&map[x][y] < baby_size)  //먹을 수 있을때
		{
			if (result_count == -1)  //처음 먹이 발견할때의 거리 저장
			{
				result_count = count;			
			}		
			
			if(result_count<count) break;  // 먹이 처음 발견했을때 count보다 count가 커지면 탈출
	
			v.push_back(make_pair(x, y)); //가장 가까운 먹이들 저장
		}

		for (int d = 0; d < 4; d++)
		{
			int nextx = x + dir[d][0];
			int nexty = y + dir[d][1];
			if (nextx < 0 || nexty < 0 || nextx >= n || nexty >= n)continue;
			if (check[nextx][nexty])continue;
			if (map[nextx][nexty] > baby_size)continue;
			check[nextx][nexty] = true;

			q.push(ins(nextx, nexty, count + 1));
		}
	}

	if (v.empty())return -1; // 먹이가 없으면 -1반환

	int tmp_x = v[0].first;
	int tmp_y = v[0].second;
	for (int i = 1; i < v.size(); i++)   //같은 거리중 가장 위에서 왼쪽 먹이 찾기
	{
		int x = v[i].first;
		int y = v[i].second;

		if (tmp_x > x)
		{
			tmp_x = x; tmp_y = y;
		}
		else if (tmp_x == x&&tmp_y>y)
		{
			tmp_x = x; tmp_y = y;
		}
	}
	baby_x = tmp_x;
	baby_y = tmp_y;
	map[baby_x][baby_y] = 0;

	baby_prey--;  //먹음
	if (baby_prey == 0)  // 진화까지 필요한 먹이가 0이라면 진화
	{
		baby_size++;
		baby_prey = baby_size;
	}

	return result_count;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 9)
			{
				baby_x = i;
				baby_y = j;
				map[i][j] = 0;
			}
		}
	}

	int time = 0;
	
	while (1)
	{
		int plus_time=bfs(baby_x,baby_y);   //먹이 찾기
		if (plus_time==-1)break;   //더이상 먹을게 없으면 종료
		else time += plus_time;    //먹는데 걸린 시간 추가
	}
	
	cout << time;

	return 0;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.