백준 16236번 : 아기 상어

문제 링크 : www.acmicpc.net/problem/16236

풀이에 참고한 링크 : www.acmicpc.net/board/view/35923

내 풀이(2021.1.29.) :

#include <iostream>
#include <queue>

using namespace std;
typedef pair<int, int> int_pair;

int map[20][20];
int visit[20][20];
int N;
int dy[] = { -1,0,1,0 };
int dx[] = { 0,-1,0,1 };
int total_time = 0;
int cy, cx;

struct comp {
	bool operator()(int_pair& a, int_pair& b) {
		if (a.first == b.first) return a.second > b.second;
		else return a.first > b.first;
	};
};

int bfs(int sy, int sx, int size) {
	priority_queue<int_pair, vector<int_pair>, comp> q;
	q.push(make_pair(sy, sx));
	visit[sy][sx] = 1;
	int time = -1;
	while (!q.empty()) {
		int sz = q.size();
		time++;
		vector<int_pair> v;
		for (int i = 0; i < sz; i++) {
			v.push_back(q.top()); q.pop();
		}
		for (int i = 0; i < sz; i++) {
			int_pair p = v[i];
			cy = p.first;
			cx = p.second;
			if (0 < map[cy][cx] && map[cy][cx] < size) return time;
			for (int j = 0; j < 4; j++) {
				int ny = cy + dy[j];
				int nx = cx + dx[j];
				if (ny < 0 || nx < 0 || ny >= N || nx >= N || map[ny][nx] > size) continue;
				if (visit[ny][nx] == 1) continue;
				q.push(make_pair(ny, nx));
				visit[ny][nx] = 1;
			}
		}
	}
	return 0;
}

void initalize_visit() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = 0;
		}
	}
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int temp; cin >> temp;
			if (temp == 9) {
				cy = i;
				cx = j;
				map[i][j] = 0;
			}
			else map[i][j] = temp;
		}
	}

	int size = 2; // 아기 상어의 크기
	int fish = 0; // 잡아 먹은 마리 수

	while (1) {
		initalize_visit();
		int time = bfs(cy, cx, size);
		if (time == 0) break;
		total_time += time;
		fish++;
		if (size == fish) {
			size++;
			fish = 0;
		}
		map[cy][cx] = 0;
	}
	cout << total_time;

	return 0;
}

- 물고기를 최초로 발견할 때까지 bfs를 수행하고, 물고기를 먹은 좌표를 기록한다.

- 물고기를 먹은 위치에서 다시 bfs를 시작하고, 이 과정을 물고기가 발견되지 않을 때까지 반복한다.

- '거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.'라는 조건이 있는데, '상-좌-하-우' 순으로 탐색을 하는 것은 이 조건을 보장하지 못한다. 4번째 입력 예제가 그 반례이다.

- 이 조건을 해결하기 위해서 좌표값이 작은 노드를 먼저 pop하는 우선순위 큐를 사용하되, BFS 트리에서 서로 다른 깊이에 속하는 노드들은 같은 큐 내에서 섞여선 안 되므로, BFS 트리의 깊이가 바뀔 때마다 큐의 모든 원소들을 pop해서 벡터에 따로 백업해놓는 식으로 구현하였다.