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

 

 

구조체 사용,

sort를 이용한 벡터 정렬 사용 

BFS,  정렬 연습에 좋은 문제!

 

 

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

int N, startY, startX;
int MAP[21][21];
int visited[21][21];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int babyShark = 2;
int mapTime, feedCnt;

struct fish			
{
	int dist;
	int y;
	int x;
};

struct Node
{
	int y;
	int x;
};

bool compare(fish a, fish b) {		// 나중에 fishes 벡터를 정렬하기 위한 함수
	if (a.dist == b.dist) {
		if (a.y == b.y)
			return a.x < b.x;
		else
			return a.y < b.y;
	}
	else {
		return a.dist < b.dist;
	}
}

vector <fish> fishes;			// 먹을 수 있는 물고기들 저장

// bfs를 돌면서 먹을 수 있는 물고기는 fishes에 저장
void bfs(int startY, int startX) {
	memset(visited, 0, sizeof(visited));
	queue <Node> q;

	q.push({ startY, startX });

	while (!q.empty()) {
		Node now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = now.y + dy[i];
			int nx = now.x + dx[i];

			if (ny < 0 || nx < 0 || ny >= N || nx >= N)
				continue;
			if ((visited[ny][nx] != 0) || (MAP[ny][nx] > babyShark))
				continue;

			if (MAP[ny][nx] != 0 && MAP[ny][nx] < babyShark) {
				fishes.push_back({ visited[now.y][now.x] + 1, ny, nx });
			}
			q.push({ ny, nx });
			visited[ny][nx] = visited[now.y][now.x] + 1;

		}
	}
}


// 아기상어 움직이는 함수
void move() {

	while (true)
	{
		fishes.clear();

		bfs(startY, startX);

		if (fishes.size() == 0)	// 상어 없을때 엄마 찾으러 종료 ~ 
			return;

		sort(fishes.begin(), fishes.end(), compare);

		fish curFeed = fishes[0];
		MAP[curFeed.y][curFeed.x] = 0;
		startY = curFeed.y;
		startX = curFeed.x;
		mapTime += curFeed.dist;
		feedCnt++;

		if (feedCnt == babyShark) {		// 자기 몸집만큼 먹으면 몸집 커지기
			babyShark++;
			feedCnt = 0;				// 먹은 개수 초기화
		}
	}
}


int main() {

	cin >> N;
	int temp;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> temp;
			MAP[i][j] = temp;
			if (temp == 9) {
				startY = i;
				startX = j;
				MAP[i][j] = 0;
			}
		}
	}

	move();
	cout << mapTime;

	return 0;
}