[BFS] 아기 상어

 

 

 

예제 입력 1

3

0 0 0

0 0 0

0 9 0

예제 출력 1

0

예제 입력 2

3

0 0 1

0 0 0

0 9 0

예제 출력 2

3

예제 입력 3

4

4 3 2 1

0 0 0 0

0 0 9 0

1 2 3 4

예제 출력 3

14

예제 입력 4

6

5 4 3 2 3 4

4 3 2 3 4 5

3 2 9 5 6 6

2 1 2 3 4 5

3 2 1 6 5 4

6 6 6 6 6 6

예제 출력 4

60

예제 입력 5

6

6 0 6 0 6 1

0 0 0 0 0 2

2 3 4 5 6 6

0 0 0 0 0 2

0 2 0 0 0 0

3 9 3 0 0 1

예제 출력 5

48

예제 입력 6

6

1 1 1 1 1 1

2 2 6 2 2 3

2 2 5 2 2 3

2 2 2 4 6 3

0 0 0 0 0 6

0 0 0 0 0 9

예제 출력 6

39

 

 

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

16236번: 아기 상어

- BFS를 여러번 돌려야한다.

- 먼저 BFS 돌려서 가장 가까운 먹을 수 있는 1개의 물고기의 위치를 가져온다. 여러개일 경우 같은 거리이면 가장 위/왼쪽이 우선이라고 했으므로 정렬해서 첫번째것만 가져오면 된다.

- 현재 위치를 잡아먹은 물고기가 있는 곳으로 업데이트하고 물고기 잡아먹는 처리를 한다. (경험치(?), size 업데이트)

- 더이상 잡아먹을 수 있는 물고기가 없을 때까지 반복한다.

 

#include <stdio.h>



const int MAX_SIZE = 20;
const int MAX_QUEUE_SIZE = 1000;

int map[MAX_SIZE][MAX_SIZE];

int N;

int dR[] = { -1, 1, 0, 0 };
int dC[] = { 0, 0, -1, 1 };

class Point
{
public:
	int r;
	int c;
	int dist;

	Point() {
		r = c = dist = 0;
	}

	Point(int r, int c) : r(r), c(c) {}

	bool isInBoundary(int N)
	{
		return (r >= 0) && (r < N) && (c >= 0) && (c < N);
	}

	bool operator<=(Point other)
	{
		if (r == other.r) return c <= other.c;
		return r <= other.r;
	}

	bool operator==(Point other)
	{
		return (r == other.r) && (c == other.c);
	}
};

class Shark : public Point
{
public:
	int size;
	int exp; 

	Shark()
	{
		r = c = 0;
		size = 2;
		exp = 0;
	}

	Shark(int r, int c, int size, int weight) : size(size), exp(exp)
	{
		this->r = r;
		this->c = c;
	}

	void eatFish(int r, int c)
	{
		
	}
};
template<typename T>
class vector
{
public:
	T items[MAX_QUEUE_SIZE];
	int size;

	vector() { size = 0; }

	void add(T item)
	{
		items[size] = item;
		size++;
	}

	void clear()
	{
		size = 0;
	}

	void mergeSort(int start, int end)
	{
		if (start >= end) return;
		int mid = (start + end) / 2;

		mergeSort(start, mid);
		mergeSort(mid + 1, end);

		int i = start;
		int j = mid + 1;
		int k = 0;

		while (i <= mid && j <= end)
		{
			if (items[i] <= items[j])
			{
				tempItems[k] = items[i];
				i++; k++;
			}
			else
			{
				tempItems[k] = items[j];
				j++; k++;
			}
		}

		while (i <= mid)
		{
			tempItems[k] = items[i];
			i++; k++;
		}

		while (j <= end)
		{
			tempItems[k] = items[j];
			j++; k++;
		}

		for (int i = start; i <= end; i++)
		{
			items[i] = tempItems[i - start];
		}
	}

private:
	T tempItems[MAX_QUEUE_SIZE];
};


template <typename T>
class Queue
{
private:
	int front;
	int rear;
	T items[MAX_QUEUE_SIZE];

public:
	Queue() { front = rear = 0; }

	void push(T item)
	{
		items[rear] = item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	T pop()
	{
		T result = items[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool isEmpty()
	{
		return front == rear;
	}
};
Queue<Shark> q;
Shark shark;
Point nop(-1, -1);

Point BFS(Shark shark, int N)
{
	int dist[MAX_SIZE][MAX_SIZE];
	int minDist = -1;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			dist[i][j] = -1;
		}
	}

	dist[shark.r][shark.c] = 0;
	q.push(shark);

	vector<Shark> targets;

	while (!q.isEmpty())
	{
		Shark now = q.pop();

		for (int i = 0; i < 4; i++)
		{
			Shark next(now.r + dR[i], now.c + dC[i], now.size, now.exp);

			if (!next.isInBoundary(N)) continue;

			if (map[next.r][next.c] == 0 && dist[next.r][next.c] == -1)
			{
				dist[next.r][next.c] = dist[now.r][now.c] + 1;
				q.push(next);
			}
			else if (map[next.r][next.c]!=0 && map[next.r][next.c] <= now.size && dist[next.r][next.c] == -1)
			{
				// 먹을 수 있다.
				if (map[next.r][next.c] < now.size)
				{
					if (minDist == -1 || minDist > dist[now.r][now.c]+1)
					{
						targets.clear();
						minDist = dist[now.r][now.c] + 1;
						targets.add(next);
					}
					else if (minDist == dist[now.r][now.c]+1)
					{
						minDist = dist[now.r][now.c] + 1;
						targets.add(next);
					}
				}
					
				dist[next.r][next.c] = dist[now.r][now.c] + 1;
				q.push(next);
			}
		}
	}

	if (targets.size == 0)
	{
		return nop;
	}
	
	targets.mergeSort(0, targets.size-1); // 가장 왼쪽 위를 찾음
	targets.items[0].dist = minDist;

	return targets.items[0];
}

int main(void)
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &map[i][j]);
			
			if (map[i][j] == 9)
			{
				shark.r = i;
				shark.c = j;
				
				map[i][j] = 0;
			}
		}
	}

	int result = 0;

	while (true)
	{
		// 먹을 수 있는 물고기를 찾는다.
		Point target = BFS(shark, N);

		if (target == nop)
		{
			break;
		}
		else
		{
			// 물고기를 먹는다.
			shark.r = target.r;
			shark.c = target.c;
			shark.exp++;

			result += target.dist;

			if (shark.exp >= shark.size)
			{
				shark.exp -= shark.size;
				shark.size++;
			}

			map[target.r][target.c] = 0;
		}
	}

	printf("%d\n", result);

	return 0;
}