[C++] 백준 16236번: 아기 상어

문제 링크

16236번: 아기 상어

문제 요약

1. 아기 상어는 자기보다 작거나 같은 물고기가 있는 인접한 칸으로만 이동이 가능하다.
2. 아기 상어는 자기보다 작은 물고기만 먹을 수 있다.
3. 아기 상어는 매 이동 시에 가장 가까운, 먹을 수 있는 물고기가 있는 곳을 향해 이동한다.
4. 3번에 해당하는 물고기가 여럿이라면 가장 위쪽, 그 다음은 가장 왼쪽을 우선하여 물고기를 먹는다.
5. 아기 상어의 초기 크기는 2이다.
6. 아기 상어가 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가한다. 먹은 물고기의 수는 크기가 증가하면 0으로 초기화된다.
7. 먹을 수 있는 물고기가 없을 때까지의 이동 거리를 출력해야 한다.

접근 방법

상기 조건에 해당하도록 구현/시뮬레이션 해주면 되는 간단한 문제였습니다. 먹을 수 있는 최단 거리의 물고기를 찾아야 하기 때문에 기본적으로 너비 우선 탐색을 사용했습니다.

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

라는 조건이 있었는데, 이를 위해서 BFS에서 우선순위큐를 이용했습니다. 우선순위 큐 내에서 원소들은 거리, 행, 열 순으로 우선순위를 두고 오름차순으로 정렬됩니다. 그것을 제외하면 보통 BFS와 거의 동일하게 작성했습니다.

작년에 한창 삼성 SW 역량 기출 풀때보다는 구현 실력이 많이 늘은거 같습니다. 당시에는 골드 구현 문제에서 막히면 2시간까지 걸렸었던 기억이 있습니다. 오늘은 조건을 확실하게 이해하고, 실수 없이 구현해서 빠르게 잘 풀린거 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Shark {
	int sz, fish, r, c;
}shark;

struct Info {
	int dist, r, c;
};

struct compare {
	bool operator()(const Info& a, const Info& b)
	{
		if (a.dist == b.dist)
		{
			if (a.r == b.r)
				return a.c > b.c;
			return a.r > b.r;
		}
		return a.dist > b.dist;
	}
};

int n, sea[21][21], res = 0, dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
bool visited[21][21];

bool bfs(void)
{
	memset(visited, false, sizeof(visited));
	priority_queue<Info, vector<Info>, compare> pq;
	pq.push({ 0, shark.r, shark.c });
	visited[shark.r][shark.c] = true;

	bool flag = false;
	while (!pq.empty())
	{
		Info now = pq.top();
		pq.pop();

		if (sea[now.r][now.c] && sea[now.r][now.c] < shark.sz)
		{
			flag = true;
			res += now.dist;
			sea[now.r][now.c] = 0;
			shark.fish++;
			shark.r = now.r;
			shark.c = now.c;

			if (shark.fish == shark.sz)
			{
				shark.fish = 0;
				shark.sz++;
			}

			break;
		}

		for (int i = 0; i < 4; i++)
		{
			Info next = { now.dist + 1, now.r + dir[i][0], now.c + dir[i][1] };
			if (next.r >= 1 && next.r <= n && next.c >= 1 && next.c <= n
				&& !visited[next.r][next.c] && sea[next.r][next.c] <= shark.sz)
			{
				visited[next.r][next.c] = true;
				pq.push(next);
			}
		}
	}

	return flag;
}

int main(void)
{
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> sea[i][j];
			if (sea[i][j] == 9)
			{
				shark = { 2, 0, i, j };
				sea[i][j] = 0;
			}
		}
	}

	while (1)
		if (!bfs())
			break;

	cout << res;
	return 0;
}