[Baekjoon] 16236번: 아기 상어

 

 

 

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

16236번: 아기 상어

 

---

 

문제 해결 과정

착안

문제에서 아기 상어가 물고기를 먹기 위해 이동하는 최소 경로가 크기에 따라 달라지는 상황에서, 아기 상어가 먹이를 찾아 탐색하는 과정을 구현하는 문제이다. 문제를 처음 접했을 때, 아기 상어의 1 초당 이동 반경을 중심으로 전방향으로 탐색을 하는 방법을 생각해보았다. 즉, 너비 우선 탐색(breadth-first search, BFS)의 원리에 기반하여 주어진 공간 내의 먹이를 탐색하는 코드를 구현하고자 주어진 조건들을 정리하여 다음과 같은 핵심적인 동작들에 중점을 두어 구현하고자 했다.

 

• 1 초당 한 칸씩 이동 $\longrightarrow 아기 상어의 시작 위치를 중심으로 마름모 모양으로 반경을 넓혀 탐색
• 단, 자신보다 크기가 큰 물고기가 있는 칸은 지나갈 수 없으므로 BFS 과정에서 해당 타일은 배제
• 물고기를 먹으면 탐색을 종료하고 이동한 시간을 누적한 뒤 해당 위치에서 새로 탐색을 시작한다
• 문제에서 주어진 우선순위에 따른 방향으로 탐색한다

 

구현

기본적으로 너비 우선 탐색 알고리즘을 구현하는 작업을 해야했지만, 주어지는 공간 내의 각각의 타일을 모두 그래프의 정점으로 만들고 연결하는 것이 비효율적이라고 생각하여 보다 간소화하여 알고리즘을 구현해보았다.

 

입력되는 공간 정보를 저장할 배열(int 형, $20 \times 20$ 크기)을 선언하여 물고기의 크기를 저장(0인 경우는 물고기가 없는 것으로 판단)하고 별도로 타일의 방문여부를 저장하기 위한 Visited 배열을 사용하였다.

 

(실패 과정) 처음 구현할 때에는 위에서 정리한 네 가지 핵심 동작들 중, 마지막 조건에 대해 크게 신경을 쓰지 않아 문제 해결에 실패했었다. 이 부분을 우선 제외하고 다른 동작에 대해서는 기본적인 너비 우선 탐색 알고리즘과 동일했으므로 큐(queue) 자료 구조를 활용하여 프로그래밍했다. 이때 큐에 현재 방문한 타일을 중심으로 위쪽 - 왼쪽 - 오른쪽 - 아래쪽 순서로 push(추상 자료형에서의 enqueue)를 하면 문제에서 요구한 것과 같은 방향으로 탐색이 이루어질 줄 알았는데 아래의 그림에서 확인할 수 있듯이 타일을 방문하는 우선순위가 일치하지 않음을 알 수 있었다.

 

글자가 작아서 잘 보이지 않는 경우는 클릭 해주쎄욤 ^______________________^

 

2 초가 걸려 이동할 수 있는 반경(초록색으로 표시한 타일)에 해당하는 공간을 탐색하는 순서에서 9, 10번째로 탐색하는 타일의 순서가 다르기 때문에 문제에서 요구하는 바를 달성하려면 이를 해결해야했다.

 

(문제 해결) 고민을 좀 해본 결과, 말 그대로 우선순위를 정해주면 해결이 가능한 문제였기 때문에 우선순위 큐를 활용해보기 위해 STL의 std::priority_queue<> 클래스를 활용하였다. 문제에서 요구하는 순서에 맞도록 이항 조건(binary predicate, 아래 코드에서 cmp 구조체)을 만들어 템플릿 매개변수로 전달함으로써 시작 위치로부터 도달하기 위한 시간이 같은 타일들 즉, 같은 우선순위를 가지는 타일들을 탐색할 때 알맞은 순서대로 너비 우선 탐색을 수행할 수 있었다.

* 참고) 이항 조건: bool 형의 리턴형을 가지는 함수 객체(펑터, functor)를 의미함.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <queue>

using namespace std;

struct Coord { int X, Y, Time; };

int N;
int Fishes[20][20];
int TotalTime;
int Level = 2, Exp;

struct cmp
{
	bool operator()(Coord a, Coord b)
	{
		if (a.Time == b.Time)
		{
			if (a.X == b.X)
				return a.Y > b.Y;

			return a.X > b.X;
		}
		return a.Time > b.Time;
	}
};

bool Search(Coord& start)
{
	priority_queue<Coord, vector<Coord>, cmp> pq;
	pq.emplace(start);

	bool Visited[20][20] = { 0, };
	while (!pq.empty())
	{
		Coord coord = pq.top();
		pq.pop();

		if (Visited[coord.X][coord.Y] ||
			Fishes[coord.X][coord.Y] > Level)
			continue;

		if (Fishes[coord.X][coord.Y] > 0 &&
			Fishes[coord.X][coord.Y] < Level)
		{
			if (++Exp == Level)
			{
				Level++;
				Exp = 0;
			}

			Fishes[coord.X][coord.Y] = 0;
			TotalTime += coord.Time;
			start = { coord.X, coord.Y, 0 };

			return true;
		}

		if (coord.X - 1 >= 0)
			pq.emplace(Coord{ coord.X - 1, coord.Y, coord.Time + 1 });

		if (coord.Y - 1 >= 0)
			pq.emplace(Coord{ coord.X, coord.Y - 1, coord.Time + 1 });

		if (coord.Y + 1 <= N - 1)
			pq.emplace(Coord{ coord.X, coord.Y + 1, coord.Time + 1 });

		if (coord.X + 1 <= N - 1)
			pq.emplace(Coord{ coord.X + 1, coord.Y, coord.Time + 1 });

		Visited[coord.X][coord.Y] = true;
	}

	return false;
}

int main()
{
	cin >> N;

	Coord start;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			int fish;
			cin >> fish;

			if (fish != 9)
				Fishes[i][j] = fish;
			else
			{
				start = Coord{ i, j, 0 };
				Fishes[i][j] = 0;
			}
		}

	while (true)
		if (!Search(start))
			break;

	cout << TotalTime;
	return 0;
}

 

실행 결과