백준 16236번: 아기 상어 (C++)

1. 문제 링크

16236번: 아기 상어

2. 소스코드

#include <iostream>
#include <queue>
#include <cstring>
#define MAXN 21
using namespace std;
int row[4] = { -1,0,1,0 };
int col[4] = { 0,-1,0,1 };
queue<pair<pair<int, int>,int>> q;
priority_queue< pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> destination;
int n, x, y, nextx,nexty,shark = 2;
int prey = 0;
int nexts,sec = 0;
int fish = 0;
int space[MAXN][MAXN];
int visited[MAXN][MAXN];
void bfs(int x, int y,int s) {
	for (int dir = 0;dir < 4;dir++) {
		if (x + row[dir] >= 0 && x + row[dir] < n && y + col[dir] >= 0 && y + col[dir] < n&&space[x+row[dir]][y+col[dir]]<=shark&&visited[x + row[dir]][y + col[dir]]==0) {
			visited[x+row[dir]][y+col[dir]] = 1;
			q.push(make_pair(make_pair(x + row[dir], y + col[dir]),s+1));
			if (space[x + row[dir]][y + col[dir]] != 0 && space[x + row[dir]][y + col[dir]] < shark) {
				destination.push(make_pair(s+1,make_pair(x + row[dir], y + col[dir]) ));
			}
		}
	}
	if (!q.empty()) {
		nextx = q.front().first.first;nexty = q.front().first.second;nexts = q.front().second;
		q.pop();
		bfs(nextx,nexty, nexts);
	}
	else {
		while (!destination.empty()) {
			nextx = destination.top().second.first;nexty = destination.top().second.second;sec+= destination.top().first;
			destination.pop();
			space[nextx][nexty] = 0;
			memset(visited, 0, sizeof(visited));
			visited[nextx][nexty] = 1;
			fish++;
			if (shark == fish) { shark++;fish = 0; }
			destination = priority_queue< pair<int,pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>>();
			bfs(nextx, nexty, 0);
		}
		return;
	}
}
int main() {
	cin >> n;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> space[i][j];
			if (space[i][j] == 1)prey++;
			else if (space[i][j] == 9) { space[i][j] = 0;x = i;y = j; }
		}
	}
	if (prey == 0) {
		cout << 0;
		return 0;
	}
	visited[x][y] = 1;
	bfs(x, y,0);
	cout << sec;
	return 0;
}

3. 노트

3-1.첫 번째 시도 (실패)

첫 시도에서는 처음 위치에서 bfs로 탐색하며 먹을 수 있는 물고기를 발견하였을 때, 그 물고기를 먹고 그 자리에서부터 다시 bfs를 실시한다.
이렇게 풀면, 문제의 조건

먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

에 위배되어, 제시된 테스트케이스에서부터 막힌다.

3-2.bfs를 이용하되, priority queue를 이용하여 조건 충족

우선 처음 위치에서 넓이 우선 탐색을 하며 먹을 수 있는 물고기의 위치를 파악한다.
먹을 수 있는 물고기의 정보는
(출발 위치에서 물고기까지의 거리,(물고기의 x좌표,물고기의 y좌표))
로 저장하고, 이를 우선순위 큐를 이용하여 오름차순으로 정렬하면 가장 거리가 가까운 물고기, 혹은 거리가 같다면 가장 위에 있는 물고기의 좌표를 얻을 수 있다.
이 물고기가 다음 목적지이다.
그 물고기까지 가서, 그 물고기까지의 거리를 총 이동 거리에 더하고, 물고기를 먹은 후(그럼 그 물고기가 있던 자리는 0이 되겠지?)
그 자리에서부터 다시 bfs를 진행하고, 먹을 수 있는 물고기의 위치를 파악하고, 다음 목적지를 설정하고....를 반복한다. 더 이상 먹을 수 있는 물고기가 없으면 탐색은 종료된다.

이 때 새로운 출발지에서 다시 bfs를 실행할 때마다, 먹을 수 있는 물고기의 정보는 처음부터 새로 구해야 한다. 먹을 수 있는 물고기까지의 거리가 갱신될 뿐더러, 아기 상어의 크기가 커짐에 따라 이전 단계에서 먹을 수 없었던 물고기를 먹을 수 있게 되기 때문이다. 따라서 단계마다 우선순위 큐는 리셋되어야 한다.
priority_queue는 clear함수가 존재하지 않으므로, 빈 우선순위 큐로 값을 재할당해주면 된다.

destination = priority_queue< pair<int,pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>>();

이렇게!!