[Baekjoon] 16236번: 아기 상어

🥅 문제

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

 

🔍 설계

초기 설계에서는 초를 늘리면서, 거리가 동일할 때는 위, 왼쪽, 오른쪽, 아래 순으로 우선순위가 높으므로, 탐색 순서도 위, 왼쪽, 오른쪽, 아래 순으로 탐색한다.

 

먹을 수 있는 것이 있으면, 바로 먹고, 거리를 반환한다.

 

먹을 수 없으면, 거리를 갱신하고, 큐에 담는다.

 

반환된 거리가 0이 아니면, 먹을 수 있는 것이 있다는 의미이므로, 최종 결과에 더한다.

반환된 거리가 0이면 먹을 수 있는 것이 더 이상 없다는 의미이므로 반복문을 종료한다.

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

int n, baby_shark_size = 2, eat_count = 0, baby_shark_x, baby_shark_y, plus_dist, result = 0;
int dx[] = { -1,0,0,1 };
int dy[] = { 0,-1,1,0 };

vector<vector<int>> space(20, vector<int>(20));
vector<vector<int>> dist(20, vector<int>(20, 1e9 + 7));

void grow() {
	if (eat_count == baby_shark_size) {
		baby_shark_size += 1;
		eat_count = 0;
	}
}

int bfs() {
	int cur_dist = 0;
	queue<pair<int, int>> q;
	q.push({ baby_shark_x, baby_shark_y });
	dist[baby_shark_x][baby_shark_y] = 0;
	
	while (!q.empty()) {
		int size = q.size();
		cur_dist += 1;
		for (int i = 0; i < size; i++) {
			int cur_x = q.front().first;
			int cur_y = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {
				int new_x = cur_x + dx[j];
				int new_y = cur_y + dy[j];
				if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < n) {
					if (dist[new_x][new_y] < cur_dist) {
						continue;
					}
					if ((space[new_x][new_y] == 0) || (space[new_x][new_y] == baby_shark_size)) {
						dist[new_x][new_y] = cur_dist;
						q.push({ new_x, new_y });
					}
					else if (space[new_x][new_y] < baby_shark_size) {
						eat_count += 1;
						baby_shark_x = new_x;
						baby_shark_y = new_y;
						space[new_x][new_y] = 0;
						grow();
						return cur_dist;
					}
				}
			}
		}
	}
	return 0;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);	

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> space[i][j];
			if (space[i][j] == 9) {
				baby_shark_x = i;
				baby_shark_y = j;
				space[i][j] = 0;
			}
		}
	}
	
	while (true) {
		dist = vector<vector<int>>(20, vector<int>(20, 1e9 + 7));
		plus_dist = bfs();

		if (plus_dist == 0) {
			break;
		}
		else {
			result += plus_dist;
		}
	}

	cout << result << "\n";

	return 0;
}

 

최종적으로 위와 같이 코드를 작성하였다. 그런데 예제 입력 4를 통과하지 못했다.

 

이유를 알아보니 

5 4 0 0 3 4
4 3 0 3 4 5
3 2 0 5 6 6
2 0 0 3 4 5
3 2 0 6 5 4
6 6 6 6 6 6

5 4 0 0 3 4
4 0 0 3 4 5
3 2 0 5 6 6
2 0 0 3 4 5
3 2 0 6 5 4
6 6 6 6 6 6

 

시작 위치는 노란색이고, 파란색이 0이 되어야 하는데, 빨간색이 0이 되었다. 빨간색과 파란색까지의 거리는 같지만, 위, 왼쪽, 오른쪽, 아래 순으로 탐색을 반복하므로, 왼쪽+아래가 오른쪽+오른쪽보다 먼저 탐색되게 된다.

---

그래서, 단순하게 처음 아기 상어의 위치에서 접근할 수 있는 모든 먹이까지의 거리를 구하고, 최소 거리를 찾는 방식으로 바꾸었다.

 

주의해야 할 것은 아기 상어가 먹이를 먹으면, 그 위치는 0으로 갱신하므로, 최소 거리를 갖는 먹이의 위치를 찾을 때, 그 칸에 있는 수가 0 보다 커야 한다는 것을 잊지 말자.

 

👊 풀이

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

int n, baby_shark_size = 2, eat_count = 0, baby_shark_x, baby_shark_y, result = 0, min_value, temp_x, temp_y;
int dx[] = { -1,0,0,1 };
int dy[] = { 0,-1,1,0 };

vector<vector<int>> space(20, vector<int>(20));
vector<vector<int>> dist(20, vector<int>(20, 1e9 + 7));

void grow() {
	if (eat_count == baby_shark_size) {
		baby_shark_size += 1;
		eat_count = 0;
	}
}

void bfs() {
	int cur_dist = 0;
	queue<pair<int, int>> q;
	q.push({ baby_shark_x, baby_shark_y });
	dist[baby_shark_x][baby_shark_y] = 0;
	
	while (!q.empty()) {
		int size = q.size();
		cur_dist += 1;
		for (int i = 0; i < size; i++) {
			int cur_x = q.front().first;
			int cur_y = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {
				int new_x = cur_x + dx[j];
				int new_y = cur_y + dy[j];
				if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < n) {
					if (dist[new_x][new_y] > cur_dist) {
						if (space[new_x][new_y] <= baby_shark_size) {
							dist[new_x][new_y] = cur_dist;
							q.push({ new_x, new_y });
						}
					}
					
				}
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);	

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> space[i][j];
			if (space[i][j] == 9) {
				baby_shark_x = i;
				baby_shark_y = j;
				space[i][j] = 0;
			}
		}
	}

	while (true) {
		dist = vector<vector<int>>(20, vector<int>(20, 1e9 + 7));

		bfs();

		min_value = 1e9 + 7;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (baby_shark_size > space[i][j] && space[i][j] > 0) {
					if (dist[i][j] > 0 && min_value > dist[i][j]) {
						baby_shark_x = i;
						baby_shark_y = j;
						min_value = dist[i][j];
					}
				}
			}
		}

		if (min_value == 1e9 + 7) {
			break;
		}

		eat_count += 1;
		space[baby_shark_x][baby_shark_y] = 0;
		grow();
		result += min_value;
	}

	cout << result << "\n";
	
	return 0;
}