[BOJ]16236번: 아기 상어 (c++)

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

16236번: 아기 상어

 

bfs로 현재 위치에서 다음 타겟 물고기 위치 검색

+ 더이상 먹을 물고기가 없을 때까지 재귀로 걸린시간 더하기

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

struct pos {
	int x, y;
};

int N;
const int MAX = 20;
int map[MAX][MAX];
int dist[MAX][MAX];
int dr_x[] = { -1, 0, 1, 0 };
int dr_y[] = { 0, -1, 0, 1 };

pos bfs_get_next_pos(pos start, int size)
{
	memset(dist, -1, sizeof(dist));

	queue<pos> q;
	q.push(start);
	dist[start.x][start.y] = 0;

	pos next = { N, N };
	bool fish = false;
	int min_dist = 987654321;	// 먹을 수 있는 물고기와의 최소거리

	while (!q.empty())
	{
		pos p = q.front();
		q.pop();

		// min_dist보다 큰 경로는 의미가 없다
		if (dist[p.x][p.y] > min_dist)
		{
			continue;
		}

		// 4방향 탐색
		for (int i = 0; i < 4; ++i)
		{
			int nx = p.x + dr_x[i];
			int ny = p.y + dr_y[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
			{
				continue;
			}

			// 이미 거리를 구했거나 물고기사이즈가 더 클 때
			if (dist[nx][ny] >= 0 || map[nx][ny] > size)
			{
				continue;
			}

			// 거리값을 저장 한 후 큐에 push
			dist[nx][ny] = dist[p.x][p.y] + 1;
			q.push({ nx, ny });

			// 먹을 수 있는 물고기이면
			if (map[nx][ny] > 0 && map[nx][ny] < size)
			{
				// 거리가 min_dst보다 크면 X
				if (dist[nx][ny] > min_dist)
				{
					continue;
				}
				// 맨 위, 맨 왼쪽의 먹을 수 있는 물고기 위치 구하기
				if ((nx < next.x || (nx == next.x && ny < next.y)))
				{
					next = { nx, ny };
					min_dist = dist[nx][ny];
				}

				fish = true;
			}
		}
	}

	// 먹을 수 있는 물고기가 없다면
	if (!fish)
	{
		next = { -1, -1 };
	}
	return next;
}

int fish_time(pos start, int size, int ate, int time)
{
	// 먹을 수 있는 다음 물고기 위치를 bfs로 탐색
	pos next = bfs_get_next_pos(start, size);
	if (next.x == -1)
	{
		return time;
	}

	// 현재 size만큼 먹으면 상어는 크기가 1 커진다
	if (++ate == size)
	{
		++size;
		ate = 0;
	}

	/*
		상어의 위치는 위에서 구한 물고기 위치로 대체.
		시간은 물고기 위치까지의 거리를 더한 값으로 fish_time 재귀호출
	*/
	map[next.x][next.y] = 0;
	return fish_time(next, size, ate, time + dist[next.x][next.y]);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	pos start;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> map[i][j];

			// 아기 상어 위치 저장 후 map[i][j]은 0으로 대체
			if (map[i][j] == 9)
			{
				start = { i, j };
				map[i][j] = 0;
			}
		}
	}

	// 먹을 수 있는 물고기를 모두 먹기까지 걸리는 시간 출력
	cout << fish_time(start, 2, 0, 0);

	return 0;
}

 

베-이비샤크 뚜루뚜뚜루뚜뚜,,,

bfs를 여러번 호출하는 문제는 처음이라서 좀 어려웠다.

 

 

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

문제의 핵심은 거리가 가장 가까운 물고기를 먹으러 가야 한다는 점이다. 

그런데 먹으러 갔다면, 새로운 위치에서 가장 가까운 물고기는 또 어떻게??

 

--> 여기서 BFS - Flood Fill을 여러번 실행해야할 이유가 생긴다.

매번 아기상어 위치가 바뀔 때마다 dist배열에 현재 상어 위치로부터의 거리를 매겨서

가장 가까운 물고기 위치를 새로 구해야한다. 

더이상 먹을 물고기가 없을 때까지!

int fish_time(pos start, int size, int ate, int time)
{
	// 먹을 수 있는 다음 물고기 위치를 bfs로 탐색
	pos next = bfs_get_next_pos(start, size);
	if (next.x == -1)
	{
		return time;
	}
   	...

 

 

 

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

BFS구현을 까다롭게 하는 요구사항이다.

다음과 같은 세부 구현사항을 추가 해준다. 

next는 BFS함수가 반환할 다음 물고기 위치이다.

// 먹을 수 있는 물고기이면
if (map[nx][ny] > 0 && map[nx][ny] < size)
{
	// 거리가 min_dist보다 크면 X
	if (dist[nx][ny] > min_dist)
	{
		continue;
	}
	// 맨 위, 맨 왼쪽의 먹을 수 있는 물고기 위치 구하기
	if ((nx < next.x || (nx == next.x && ny < next.y)))
	{
		next = { nx, ny };
		min_dist = dist[nx][ny];
	}
}

 

 

 

유용했던 반례

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

answer:0