[BAEKJOON][C++][시뮬레이션] 16236번 아기상어

문제

16236번: 아기 상어

 

풀이

이 문제를 풀 때 중요한 점은, 물고기를 한마리 먹을 때 마다 그리고 물고기 크기가 늘었을 때 마다 먹을 수 있는 물고기를 재탐색해야 한다는 것이다.

 

물고기를 한 마리 먹었으면, 그자리로 이동해서 다시 가장 가까운 && 가장 위에 있는 && 가장 안쪽에 있는 물고기를 다시 찾아야하기 때문이다. 그리고 물고기 크기가 늘었다면, 먹을 수 있는 물고기가 늘어날 것이기 때문이다.

 

물고기를 탐색하는 부분은, 가장 가까운 물고기가 최우선이므로 최단거리 찾기에 쓰이는 BFS 를 이용했다.

 

• 변수 설명

1. 탐색할 때마다 상어가 갖고 있어야할 변수(좌표, 사이즈, 먹은 물고기수, 시간)가 많아서 구조체로 상어변수를 표현했다. 물고기도 좌표, 거리 변수를 갖고 있어야 해서 구조체로 표현했다. 

typedef struct {
	int x;
	int y;
	int size;
	int eating_num;
	int time;
}Shark;

typedef struct {
	int x;
	int y;
	int distance;
}Fish;

 

2. 찾은 물고기들의 떨어진 거리가 같을 경우 문제의 조건대로 정렬해야하므로 물고기들을 저장해 놓을 벡터 변수를 만들었다.

vector<Fish> fish_vector;

그리고 정렬은 sort함수를 custom해서 구했다.

//sort(fish_vector.begin(), fish_vector.end(), sortFish);


bool sortFish(Fish fish1, Fish fish2) {
	//1. distance가 가장 작은 것.
	if (fish1.distance < fish2.distance) {
		return true;
	}
	else if (fish1.distance > fish2.distance) {
		return false;
	}
	else {//같을 때
		//2. 가장 위에 있는 것. i가 가장 작은 것.
		if (fish1.x < fish2.x) {
			return true;
		}
		else if (fish1.x > fish2.x) {
			return false;
		}
		else {//같을 때
			//3. 가장 왼쪽에 있는 것. j가 가장 작은 것.
			if (fish1.y < fish2.y) {
				return true;
			}
			else if (fish1.y > fish2.y) {
				return false;
			}
			else return false;
		}
	}
}

 

• 로직설명

1. 문제에서 주어진 Input을 받는다. 이 때, 상어의 위치에서 BFS를 탐색해야 하므로 상어의 위치가 들어왔을 때, 상어 구조체 변수를 해당 위치로 초기화해준다.

2. Input을 받을 때, 먹을 수 있는 물고기 수도 갱신해줘서 물고기수가 1개 이상이라면 BFS로 탐색을 진행하고, 아닐경우 0을 출력하도록 해줬다.

3. 먹을 수 있는 물고기 수가 있다면, BFS로 물고기들을 찾는다.

int direction[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; //상하좌우 방향키
queue<pair<pair<int, int>,int>> move_q; //이동할 수 있는 칸들을 저장할 변수(칸의 x좌표, y좌표, 이동 거리)
bool visited[MAX_SIZE][MAX_SIZE]; //방문여부를 체크할 변수

  3-1 상하좌우 방향키로 이동하다가 해당 자리가 0이 아니고, 자기보다 작은 수를 만났을 때, 해당 칸의 정보를 물고기 변수를 하나 만들고 벡터에 저장해준다. 이 때, 이동거리가 1씩 늘어나니깐 dist(거리변수)에 1 늘린 값을 저장해준다.

Fish fish = {next_x, next_y, dist+1};
fish_vector.push_back(fish);

4. 탐색이 모두 끝났다면, 물고기를 정렬해서 맨 앞에 있는 물고기를 먹으러 간다.

5. 물고기를 먹을 때, 상어의 정보를 갱신해준다.

shark.x = fish_vector.front().x;
shark.y = fish_vector.front().y;
shark.eating_num += 1;
shark.time += fish_vector.front().distance;
map[shark.x][shark.y] = 9;

   5-1 물고기를 먹었는데 상어가 먹은 물고기 수와 자기 몸 크기가 같아졌다면, 먹은 개수를 0으로 초기화해주고 다시 BFS로 물고기를 찾으러 간다.

if (shark.eating_num == shark.size) { 
	shark.size += 1;
	shark.eating_num = 0;
	SearchBFS();//물고기 크기가 늘면 물고기 다시 찾아야 함
}

 

 

전체 코드

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

typedef struct {
	int x;
	int y;
	int size;
	int eating_num;
	int time;
}Shark;

typedef struct {
	int x;
	int y;
	int distance;
}Fish;

const int MAX_SIZE = 21;
int direction[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };//상하좌우 방향키
int map_size;
int map[MAX_SIZE][MAX_SIZE];

Shark shark;
vector<Fish> fish_vector;//먹을 수 있는 물고기들을 저장할 배열(정렬을 위해 벡터에 저장)

int SearchBFS();//물고기 탐색
void eatFish();//물고기 먹기

//물고기 정렬
bool sortFish(Fish fish1, Fish fish2) {
	//1. distance가 가장 작은 것.
	if (fish1.distance < fish2.distance) {
		return true;
	}
	else if (fish1.distance > fish2.distance) {
		return false;
	}
	else {//같을 때
		//2. 가장 위에 있는 것. i가 가장 작은 것.
		if (fish1.x < fish2.x) {
			return true;
		}
		else if (fish1.x > fish2.x) {
			return false;
		}
		else {//같을 때
			//3. 가장 왼쪽에 있는 것. j가 가장 작은 것.
			if (fish1.y < fish2.y) {
				return true;
			}
			else if (fish1.y > fish2.y) {
				return false;
			}
			else return false;
		}
	}
}

int main() {
	int fish_num = 0;
	cin >> map_size;
	for (int i = 0; i < map_size; i++) {
		for (int j = 0; j < map_size; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {//9가 상어 위치. 상어초기화.
				shark.x = i;
				shark.y = j;
				shark.size = 2;
				shark.eating_num = 0;
				shark.time = 0;
			}
			//상어가 먹을 수 있는(자기보다 작은 물고기) 물고기 수 갱신
			if (map[i][j] > 0 && map[i][j] < 2) {
				fish_num++;
			}
		}
	}
	while (fish_num > 0) {//하나라도 있다면 먹으러 가기
		fish_num = SearchBFS();
	} cout << shark.time;

	return 0;
}

//BFS로 먹을 수 있는 가장 가까운 물고기 찾기(자신의 크기보다 작은 물고기)
int SearchBFS() {
	queue<pair<pair<int,int>,int>> move_q;//BFS 이동을 위한 큐(x,y, distance)
	bool visited[MAX_SIZE][MAX_SIZE] = { false, };//방문체크 배열
	fish_vector.clear();//물고기 다시 담아야하니깐 clear

	move_q.push(make_pair(make_pair(shark.x, shark.y),0));//현재 위치부터 탐색 시작
	map[shark.x][shark.y] = 0;//현재 위치에서 이동할거니까 0으로 표시
	visited[shark.x][shark.y] = true;//현재 위치 방문체크

	while(!move_q.empty()){//탐색할 위치가 없을 때까지 반복
		int cur_x = move_q.front().first.first;
		int cur_y = move_q.front().first.second;
		int dist = move_q.front().second;
		move_q.pop();

		for (int i = 0; i < 4; i++) {//상하좌우 탐색
			int next_x = cur_x + direction[i][0];
			int next_y = cur_y + direction[i][1];
			if (next_x >= 0 && next_x < map_size && next_y >= 0 && next_y < map_size ) {
				//상어가 이동할 수 있는 곳: 자신의 크기보다 작은 칸 & 방문한 적 없는 칸
				if (map[next_x][next_y] <= shark.size && !visited[next_x][next_y]) {
					visited[next_x][next_y] = true;
					move_q.push(make_pair(make_pair(next_x, next_y), dist+1));
					//그 자리가 0이 아니고(빈자리X) 자기보다 작은 물고기가 있다면, 물고기 벡터에 넣어주기. 
					if (map[next_x][next_y] != 0 && map[next_x][next_y] < shark.size) {
						Fish fish = {next_x, next_y, dist+1};
						fish_vector.push_back(fish);
					}
				}
			}
		}
	}
	//탐색할 수 있는 곳을 다 봤다면, 물고기 정렬해서 먹으러 가기.
	if (fish_vector.size() >= 1) {
		//물고기 정렬 후 먹기
		sort(fish_vector.begin(), fish_vector.end(), sortFish);
		eatFish();
		return fish_vector.size() - 1;
	}
	return 0;
}

//맨 첫번째 물고기 먹기
void eatFish() {
	shark.x = fish_vector.front().x;
	shark.y = fish_vector.front().y;
	shark.eating_num += 1;
	shark.time += fish_vector.front().distance;
	map[shark.x][shark.y] = 9;

	if (shark.eating_num == shark.size) { 
		shark.size += 1;
		shark.eating_num = 0;
		SearchBFS();//물고기 크기가 늘면 물고기 다시 찾아야 함
	}
}

 

cf) 애먹은 부분...

vector<Fish> fish_vector; 먹을 수 있는 물고기들을 저장한 벡터를 SearchBFS() 함수 안에 적었다가 물고기 크기가 늘어서 SearchBFS() 를 다시 수행한 후 return 하는 부분에서 이전에 들고 있던 fish_vector값을 리턴해서 main()의 재탐색문을 수행하지 않는 문제가 있었다.

↑ 14까지 가야하는데, 10에서 fish_vector.size()-1 = 0을 main 으로 리턴함... 이전에 구했던 fish_vector.size(): 1 때를 리턴해서...

 

vector<Fish> fish_vector; 를 전역변수로 빼서 main()의 재탐색문에서 fish_vector의 사이즈를 체크해줌으로써 이전 값을 return 하는 문제를 해결할 수 있었따.

 

더 좋은 방법이 있겠지만.... 3시간 끙끙거린 지금 내머리는 이게 한계인듯...