[PS][기출문제][삼성]/[BOJ][16236][아기 상어]

boj16236.cpp

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

int map[20][20];
int dmap[20][20];
bool visited[20][20];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0, 0, 1, -1 };
int n = 0;
queue<pair<pair<int, int>, int> > q;
class SHARK {
public:
	int x, y, z,cnt;
	SHARK() {
		x = y = cnt = 0;
		z = 2;
	}
	SHARK(int x, int y, int z, int cnt) :x(x), y(y), z(z), cnt(cnt) {}
};

class FISH {
public:
	int x, y,d;
	FISH() {
		x = y = d = 0;
	}
	FISH(int x, int y, int d) :x(x), y(y), d(d) {}
};

SHARK shark;
vector<FISH> fish;

bool in_range(int x, int y) {
	return 0 <= x && x < n && 0 <= y && y < n;
}

void bfs(int x, int y) {
	//dfs2bfs
	int k, nx, ny;
	int d;
	q.push(make_pair(make_pair(x, y),0));
	while (!q.empty()) {
		x = q.front().first.first;
		y = q.front().first.second;
		d = q.front().second;
		q.pop();
		if (1 <= map[x][y] && map[x][y] <= 6) {
			if (map[x][y] < shark.z) {
				fish.push_back(FISH(x, y, d));
			}
		}
		for (k = 0; k < 4; k++) {
			nx = x + dx[k];
			ny = y + dy[k];
			if (!in_range(nx, ny)) continue;
			if (visited[nx][ny]) continue;
			if (map[nx][ny] <= shark.z) {
				visited[nx][ny] = true;
				q.push(make_pair(make_pair(nx, ny), d + 1));
			}
		}
	}
}

bool compare(FISH a, FISH b) {
	if (a.d != b.d) return a.d < b.d;
	else if (a.x != b.x) return a.x < b.x;
	else return a.y < b.y;
}

int solve(void) {
	int ret = 0;
	while (true) {
		memset(visited, false, sizeof(visited));
		bfs(shark.x, shark.y);
		int fishSize = fish.size();
		if (fishSize == 0) break;
		else if (fishSize != 1) {
			sort(fish.begin(), fish.end(), compare);
		}
		map[shark.x][shark.y] = 0;
		shark.x = fish.front().x;
		shark.y = fish.front().y;
		map[shark.x][shark.y] = 9;
		shark.cnt++;
		if (shark.cnt == shark.z) {
			shark.z++;
			shark.cnt = 0;
		}
		ret += fish.front().d;
		fish.clear();
	}
	return ret;
}

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio("false");
	int i = 0, j = 0;
	cin >> n;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				shark.x = i;
				shark.y = j;
			}
		}
	}
	cout << solve();
	return 0;
}