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

문제 바로가기

16236번: 아기 상어

---

문제

NxN 크기의 공간에 물고기 M 마리와 아기 상어 1마리가 있다.

아기 상어의 처음 크기는 2이고, 1초에 한 칸씩 이동하며 물고기를 먹는 시간은 무시한다.

아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있으며, 자기 크기만큼 물고기를 먹으면 크기가 1 커진다.

아기 상어의 이동방향 결정 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.

• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.

• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.

  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.

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

---

입력

2 ≤ N ≤ 20

• 0: 빈 칸

• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기

• 9: 아기 상어의 위치

---

접근

아기 상어의 초기 위치부터 시작하여 너비 우선 탐색을 한다. 상하좌우의 각 칸에 있는 물고기가 아기 상어의 크기와 같거나 작다면 대기열 큐에 그 칸을 추가한다. 해당 칸을 방문했는지 여부를 나타내는 공간에 아기 상어의 위치로부터 얼마나 떨어졌는지를 기록한다. 같은 거리에 있는 먹을 수 있는 물고기의 위치를 기억했다가, 그 중 가장 왼쪽 그리고 위쪽에 있는 물고기를 먹는다. 먹은 물고기의 수가 아기 상어의 크기와 같다면 아기 상어의 크기를 키우고 먹은 물고기의 수를 0으로 만든다. 합계 시간에 해당 칸까지의 거리를 저장한다. 한 칸에 1초씩 걸리니까. 먹은 물고기의 위치로 아기 상어를 옮기고 더 이상 먹을 수 있는 물고기가 없을 때까지 반복한다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; i++)
#define INF 987654321
#define EL "\n"

typedef tuple<int, int, int> SHARK;		// row, col, size

int N;
int space[20][20];
int mark[20][20];
const int adjoins[4][2] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };

void initMark() {
	FOR(i, 20)
		FOR(j, 20)
		mark[i][j] = -1;
}

bool isVaildPosition(int r, int c) {
	if (r < 0 || r >= N)
		return false;
	if (c < 0 || c >= N)
		return false;
	return true;
}

int main() {
	FAST_IO;

	cin >> N;

	SHARK shark;
	FOR(r, N) {
		FOR(c, N) {
			cin >> space[r][c];
			if (space[r][c] == 9)
				shark = make_tuple(r, c, 2);
		}
	}

	int eaten = 0;
	int totalTime = 0;
	while (true) {
		initMark();
		queue<pair<int, int>> BFS;
		BFS.push(make_pair(get<0>(shark), get<1>(shark)));
		mark[get<0>(shark)][get<1>(shark)] = 0;
		vector<pair<int, int>> next;
		while (BFS.size()) {
			auto [r, c] = BFS.front();
			// 기준 위치로부터 상,좌,우,하 순서대로 방문한다.
			for (const auto d : adjoins) {
				int chg_r = r + d[0];
				int chg_c = c + d[1];
				if (isVaildPosition(chg_r, chg_c)) {
					// 방문하려는 위치의 물고기가 아기 상어의 크기보다 같거나 작은지 확인한다.
					if (get<2>(shark) >= space[chg_r][chg_c]) {
						// 만약 이미 방문했던 위치라면 패스한다.
						if (mark[chg_r][chg_c] != -1)
							continue;
						// 방문하지 않은 위치라면 대기열 큐에 추가한다.
						BFS.push(make_pair(chg_r, chg_c));
						// 큐에 넣으면서 방문 체크를 해줘야 중복이 발생하지 않는다.
						mark[chg_r][chg_c] = mark[r][c] + 1;
						// 해당 위치에 아기 상어가 먹을 수 있는 물고기가 있는지 확인한다.
						if (space[chg_r][chg_c] != 0 && space[chg_r][chg_c] < get<2>(shark)) {
							// 기존에 담겨 있는 물고기의 위치보다 거리가 멀다면 탈출
							// 그렇지 않다면 추가로 위치를 담는다.
							if (next.size()) {
								auto [_r, _c] = *next.begin();
								if (mark[chg_r][chg_c] > mark[_r][_c])
									goto OUT;
							}
							next.push_back(make_pair(chg_r, chg_c));
						}
					}
				}
			}
			BFS.pop();
		}
	OUT:
		// 거리가 같은 물고기들 중 최좌상단에 위치한 물고기를 먹는다.
		if (next.empty())
			break;
		sort(next.begin(), next.end());
		auto [r, c] = *next.begin();
		next.clear();
		// 그 거리를 합계 시간에 추가한다. (1칸에 1초이므로)
		totalTime += mark[r][c];
		// 아기 상어의 위치를 그 칸으로 이동시킨다.
		space[r][c] = 9;
		space[get<0>(shark)][get<1>(shark)] = 0;
		// 아기 상어의 크기를 키울 수 있다면 키운다.
		eaten++;
		if (eaten == get<2>(shark)) {
			get<2>(shark)++;
			eaten = 0;
		}
		shark = make_tuple(r, c, get<2>(shark));
	}

	cout << totalTime << EL;

	return 0;
}