백준 16236번: 아기 상어

[문제 링크]

16236번: 아기 상어

---

단순히 위, 왼쪽, 오른쪽, 아래 순으로 탐색하다가 먹을 수 있는 물고기가 발견되면 그 물고기가 문제 조건에 맞는 물고기라 생각하고 풀었다가 고생한 문제였다.

 

그래서 현재 상태에서 먹을 수 있는 물고기들의 위치를 모두 우선순위큐에 담은 다음 가장 우선순위가 높은 물고기를 먹는 방식으로 구현하여 정답을 받을 수 있었다.

 

bfs를 계속 반복하면서 물고기를 먹다가 만약 bfs를 했는데 우선순위큐가 비어있다면 맵에 먹을 수 있는 물고기가 없는 것이므로 반복을 종료하고 그동안 움직인 횟수를 출력하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Shark {
	int y;
	int x;
	int level;
	int exp;
	int move;

	// 물고기를 먹는다.
	// 경험치가 레벨과 같아지면 레벨업
	void eatFish() {
		exp++;
		if (level == exp) {
			level++;
			exp = 0;
		}
	}
};

// priority_queue 크기 비교를 위한 연산자 오버로딩
bool operator< (const Shark& lhs, const Shark& rhs) {
	if (lhs.move > rhs.move)
		return true;
	else if (lhs.move == rhs.move && lhs.y > rhs.y)
		return true;
	else if (lhs.move == rhs.move && lhs.y == rhs.y && lhs.x > rhs.x)
		return true;

	return false;
}

Shark shark;
int N;
int board[20][20];
// 문제 조건에 따라 북 서 동 남 순으로 탐색
int dy[4] = { -1, 0, 0, 1 };
int dx[4] = { 0, -1, 1, 0 };

bool bfs() {
	vector<vector<bool>> visited(20, vector<bool>(20, false));
	visited[shark.y][shark.x] = true;

	queue<Shark> q;
	q.push(shark);

	// 먹이로 가능한 좌표를 우선순위가 큰 순서대로 저장
	priority_queue<Shark> pq;

	while (!q.empty()) {
		Shark here = q.front();
		int fish = board[here.y][here.x];
		q.pop();

		if (fish != 0 && fish < here.level) {
			pq.push(here);
			continue;
		}

		for (int i = 0; i < 4; i++) {
			int ny = here.y + dy[i];
			int nx = here.x + dx[i];

			if (ny >= 0 && ny < N && nx >= 0 && nx < N)
				if (!visited[ny][nx] && board[ny][nx] <= here.level) {
					visited[ny][nx] = true;
					q.push({ ny, nx, here.level, here.exp, here.move + 1 });
				}
		}
	}

	if (!pq.empty()) {
		Shark pick = pq.top();
		board[pick.y][pick.x] = 0;
		shark = pick;
		shark.eatFish();
		return true;
	}

	return false;
}

int main(void) {
	cin >> N;

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

			if (board[i][j] == 9) {
				board[i][j] = 0;
				shark = { i, j, 2, 0, 0 };
			}
		}
	while (1) if (!bfs()) break;
	
	cout << shark.move << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 164 day