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

# 문제링크

www.acmicpc.net/problem/16236

16236번: 아기 상어

BFS로 같은 거리를 탐색합니다. 탐색하다가 먹을 수 있는 물고기가 나오면 vector 에 넣어뒀다가, 같은 거리탐색이 끝나면 vector 중에서 물고기를 골라서 먹고, 아기상어 위치를 해당 물고기 위치로 옮겨서 다시 탐색을 시작합니다. 

 

# 제출 코드 

 

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

struct shark {
	int size;
	int eat;
	int time;
};
shark baby = { 2, 0, 0 };
int map[25][25];
int visited[25][25];

int N;
queue <pair<int, int>> q;
int fish;
vector <pair<int, int>> v;

void Input() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9) { 
				map[i][j] = 0; 
				q.push({ i,j }); 
				visited[i][j] = 1; 
			}
			else if (map[i][j] != 0) { fish++; }
		}
	}
}
int yd[] = { -1, 0, 0, 1 };
int xd[] = { 0, -1 ,1, 0 };
int BFS() {
	int time = 1;
	bool flag = 0;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		if (fish == 0)break;

		if (visited[y][x] != time)
			if (flag) {
				sort(v.begin(), v.end()); // 같은 거리에 있는 물고기 정렬

				int ny = v[0].first;
				int nx = v[0].second;

				map[ny][nx] = 0;
				baby.eat++;
				if (baby.eat == baby.size) { baby.size++; baby.eat = 0; }
				baby.time += (visited[ny][nx] - 1);
				fish--;

				memset(visited, 0, sizeof(visited));
				visited[ny][nx] = 1;
				time = 1;
				while (!q.empty()) q.pop();
				q.push({ ny,nx });
				while (!v.empty())v.pop_back();
				flag = 0;
				continue;
			}
			else time = visited[y][x];

		for (int i = 0; i < 4; i++) {
			int ny = y + yd[i];
			int nx = x + xd[i];

			if (ny < 0 || ny >= N)continue;
			if (nx < 0 || nx >= N) continue;
			if (visited[ny][nx] != 0)continue;
			if (map[ny][nx] > baby.size)continue;

			if (map[ny][nx] != 0 && map[ny][nx] < baby.size) {
				v.push_back({ ny,nx }); // 먹을 수 있다
				flag = 1;
			}
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ ny,nx });
		}
	}
	return baby.time;
}
int main() {
	Input();
	printf("%d\n", BFS());
	return 0;
}