Baekjoon 16236 아기상어

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

소스결과 1988 KB / 4 ms

언어 C++ 17

출처 Baekjoon

분류 BFS, 시뮬레이션

 

설명

작고 귀여운 아기상어가 혼자 힘으로 물고기를 먹으며 얼마나 있는지 출력해주자.

 

삼성 A형 출제 문제 답게 문제를 열심히 읽어야한다. 다시 한번 더 느꼈다.

먼저 주어진 조건을 생각해보면

- 아기 상어는 자신의 몸집보다 작은 물고기만 먹을 수 있다.

- 아기 상어는 자신의 몸집보다 작거나 같은 물고기만 지나갈 수 있다.

- 아기 상어는 자기 몸집만큼 물고기를 먹으면 몸집이 커진다.

- 아기 상어가 물고기를 먹으면 그 자리는 빈 칸이 된다.

- 먹을 수 있는 물고기가 여러마리라면 상단, 상단 중 여러마리라면 좌측이 우선순위가 높다.

- 아기 상어는 물고기를 더이상 먹을 수 없으면 끝난다.

 

처음에는 문제를 풀 때 두번째 조건을 잘못봐서 몸집에 상관 없이 지나갈 수 있는거로 판단해 절댓값을 이용해서 구했고 결과는 TC조차 맞지 않았다.

두번째 조건을 해결해야 하기 때문에 BFS를 이용했다. 생각보다 타임아웃이 까다로워서 DFS로는 시간소요가 커보였다.

또한 우선순위를 판별할 때 미리 거리를 구한 후 하려 했는데 다시 생각해보니 0,0부터 순서대로 읽으면 되는 부분이었다.

조심해야 할 부분은 BFS를 이용해서 거리를 구할 때 였는데 물고기를 먹을 수 있는 상황이어도 갈 수가 없는 상황에 대해서도 생각을 해줘야 한다. 여기서 무한루프에 처음으로 빠졌다.

또, 반복문 조건으로 물고기의 수를 크기별로 미리세는 방법을 이용해서 더이상 먹을 수 있는 물고기가 없을 때 종료하는 방식으로 코드를 구성 했는데, 먹을 수 있는 물고기가 있어도 못먹는 경우가 존재 했었다. 여기서 무한루프에 다시 빠졌다.

 

저 두 무한루프 조건과 거리 구하는 방법을 바꾸고 나서야 코드가 통과됬다.

 

알고리즘

1. 처음 상태를 입력 받는다.

2. 상태를 입력 받으면서 크기별 물고기 수와, 시작 지점을 저장한다.

3. 0,0 부터 n,n 까지 행을 먼저 탐색하며 진행한다. 먹을 수 있는 물고기가 없을 경우 종료한다.

 3.1 현재 상어 크기보다 작을 경우 i,j까지의 거리를 구한다.

  3.1.1 BFS로 거리를 구하며, 현재 상어 크기와 같거나 작은 경우에만 지나갈 수 있도록 한다.

  3.1.2. 닿을 수 없는 경우 최대 거리인 400보다 큰 값으로 반환한다.

 3.2 거리가 400보다 작은 값이 올 경우 최소 거리와 비교를 해 목표 지점과 거리를 갱신한다.

 3.3 어디로도 갈 수 없는 경우라면 종료한다. ( 초기 최소 거리가 변하지 않은 경우 )

4. 출력

 

소스코드

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

const short MAX = 20;

int n;
short board[MAX][MAX];
short fishCount[7];
short sharkSize = 2;
short eatCount = 0;

short posX[4] = { 1, 0 ,-1, 0 };
short posY[4] = { 0, 1, 0, -1 };

struct Point {
	short x;
	short y;

	Point() : x(-1), y(-1) {}
	Point(short x, short y) : x(x), y(y) {}
};

bool continueable(int size) {

	for (int i = 0; i < size; i++)
		if (fishCount[i] > 0)
			return true;
	return false;
}

int getDistance(Point start, Point des) {

	int dist = 0;
	bool check[MAX][MAX] = { };

	queue<Point> q;
	queue<Point> nQ;
	bool isOver = false;
	bool isReachAble = true;

	q.push(start);
	check[start.x][start.y] = true;

	while (!isOver && isReachAble) {

		while (!q.empty()) {

			Point cur = q.front();
			q.pop();

			if (cur.x == des.x && cur.y == des.y)
			{
				isOver = true;
				break;
			}

			for (short i = 0; i < 4; i++) {
				short nextX = cur.x + posX[i];
				short nextY = cur.y + posY[i];

				if (0 <= nextX && nextX < n && 0 <= nextY && nextY < n && !check[nextX][nextY] && board[nextX][nextY] <= sharkSize) {
					check[nextX][nextY] = true;
					nQ.push(Point(nextX, nextY));
				}
			}
		}

		if (isOver)
			continue;

		while (!nQ.empty()) {
			q.push(nQ.front());
			nQ.pop();
		}

		if (q.empty())
			isReachAble = false;

		dist++;
	}

	if (!isReachAble)
		dist = 4000;

	return dist;
}

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

	Point shark;

	cin >> n;
	int res = 0;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];

			if (board[i][j] == 9)
			{
				shark.x = i;
				shark.y = j;
				board[i][j] = 0;
			}
			else if (board[i][j]) {
				fishCount[board[i][j]]++;
			}
		}

	while (continueable(sharkSize))
	{
		Point shortestFish;
		int shortest = 500;
		int dist = 0;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
			{
				if (board[i][j] && board[i][j] < sharkSize && abs(shark.x - i) + abs(shark.y - j) < shortest)
				{
					dist = getDistance(shark, Point(i, j));

					if (dist < 400 && shortest > dist)
					{
						shortest = dist;
						shortestFish.x = i; shortestFish.y = j;
					}
				}
			}

		if (shortest == 500)
			break;

		shark = shortestFish;
		eatCount++;
		if (eatCount == sharkSize)
		{
			eatCount = 0;
			sharkSize++;
		}
		res += shortest;

		fishCount[board[shortestFish.x][shortestFish.y]]--;
		board[shortestFish.x][shortestFish.y] = 0;
	}

	cout << res;

	return 0;
}