백준 16236번 : 아기 상어

• sol : 31' 21''

Learnings

#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <algorithm>
#include <climits>

#define SHARK 9
#define EMPTY 0
#define MAX_N 21

using namespace std;

int n;
int grid[MAX_N][MAX_N];
int sec;
bool visited[MAX_N][MAX_N];
// 상, 좌, 하, 우
int ds[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };

struct Shark {
	int r;
	int c;
	int size;
	int eatNum;

	Shark() {}
	Shark(int _r, int _c, int _size, int _eatNum) :
		r(_r), c(_c), size(_size), eatNum(_eatNum) {
	}
};

Shark babyShark;

void Init() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == SHARK) {
				babyShark = Shark(i, j, 2, 0);
			}
		}
	}
}

void InitVisited() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited[i][j] = false;
		}
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

bool CanGo(int i, int j) {
	return InGrid(i, j) && grid[i][j] <= babyShark.size && !visited[i][j];
}

void Eating(int ns, int ni, int nj) {
	babyShark.eatNum++;
	if (babyShark.eatNum == babyShark.size) {
		babyShark.size++;
		babyShark.eatNum = 0;
	}

	grid[babyShark.r][babyShark.c] = EMPTY;
	babyShark.r = ni, babyShark.c = nj;
	grid[ni][nj] = SHARK;

	sec += ns;
}

bool Eat() {
	queue<tuple<int, int, int>> q;
	q.push({ babyShark.r, babyShark.c, 0 });

	InitVisited();
	visited[babyShark.r][babyShark.c] = true;

	// dist, i, j
	tuple<int, int, int> fish = { INT_MAX, -1, -1 };;

	while (!q.empty()) {
		int ci, cj, cs;
		tie(ci, cj, cs) = q.front();
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1], ns = cs + 1;

			if (CanGo(ni, nj)) {
				visited[ni][nj] = true;
				q.push({ ni, nj, ns });

				if (grid[ni][nj] != EMPTY && grid[ni][nj] < babyShark.size) {
					tuple<int, int, int> curFish = make_tuple(ns, ni, nj);
					if (fish > curFish) fish = curFish;
				}
			}
		}
	}

	int bs, bi, bj;
	tie(bs, bi, bj) = fish;
	if (bi == -1) return false;
	else {
		Eating(bs, bi, bj);
		return true;
	}
}

int main() {
	Init();

	while (true) {
		if (!Eat()) break;
	}

	cout << sec;

	return 0;
}