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

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

---

 문제 풀이

문제에서 중요한 것은 2가지이다. 바로, BFS 구현과 우선순위를 정하는 것.

아기 상어의 정보와 물고기의 정보를 구조체로 구현했다. 구조체라는 틀에서 모든 정보를 가지기 위함이다.

함수 BFS에서는 배열 dx와 dy를 통해서 상하좌우를 한 칸씩 탐색한다.

 

탐색 도중에 나올 수 있는 경우는 4가지로,

 1. 빈 칸인 경우 : 방문했음을 체크하고, 이동거리만 추가해준다.

 2. 아기상어의 크기보다 작은 경우 : 벡터에 물고기의 정보를 추가해주고 방문했음을 체크한다.

 3. 아기상어와 크기가 같은 경우 : 먹을 순 없으므로 방문했음만을 체크한다.

 4. 아기상어보다 크기가 큰 경우 : 지나갈 수 없으므로 어떠한 동작도 하지 않는다.

 

BFS를 통해서 먹을 수 있는 물고기를 체크했다면 우선순위를 정해야 한다.

이를 구현하기 위해서 priority_queue를 사용해도 상관없지만 벡터와 sort로 구현했다.

여기서 vector의 type이 구조체이기 때문에 특별한 함수가 필요하다.

문제에서 주어진 조건은 가장 가까운, 가장 위, 가장 왼쪽에 위치 물고기 순서이다.

해당 조건을 만족하는 함수를 구현해주면 된다.

 

마무리로 구현한 벡터 즉, 먹을 수 있는 물고기의 정보가 들어간 벡터의 크기가 0이라면 

반복을 종료하고 이동한 거리를 출력하면 된다.

 느낀 점

제대로 된 구현 문제를 풀었다. BFS에 대해서 제대로 공부를 한 적이 없어서 이번에 많이 부족함을 느꼈다. 제대로된 알고리즘 이해도 없이 하다 보니 정말 푸는데 오래 걸렸다. 특히 memset함수는 for문에 비해서 시간을 적게 잡아먹는다. <cstring>을 추가해서 사용해야 한다!

 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

typedef struct {
	int x, y;
	int size;
	int eat_n;
	int t;
}Shark;

typedef struct {
	int x, y;
	int dist;
}Food;

int n;
int map[21][21];
bool visited[21][21];

Shark s;
vector<Food> v;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

bool sorting(Food a, Food b) {
	if (a.dist <= b.dist) {
		if (a.dist == b.dist) {
			if (a.x <= b.x) {
				if (a.x == b.x) {
					if (a.y < b.y) {
						return true;
					}
					return false;
				}
				return true;
			}
			return false;
		}
		return true;
	}
	return false;
}

void BFS(int a, int b) {
	queue<pair<pair<int, int>, int>>q;
	q.push(make_pair(make_pair(a, b), 0));
	visited[a][b] = true;

	while (!q.empty()) { 
		int x = q.front().first.first;
		int y = q.front().first.second;
		int dist = q.front().second; 
		// 현재 x, y좌표, 총 움직인 거리
		q.pop();

		for (int i = 0; i < 4;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
				if (visited[nx][ny] == false) {
					if (map[nx][ny] == 0) { // 빈공간
						visited[nx][ny] = true;
						q.push(make_pair(make_pair(nx, ny), dist + 1));
					}
					else if (map[nx][ny] < s.size) { // 아기상어보다 크기가 작은 물고기
						Food tmp;
						tmp.x = nx;
						tmp.y = ny;
						tmp.dist = dist + 1;

						v.push_back(tmp);
						visited[nx][ny] = true;
						q.push(make_pair(make_pair(nx, ny), dist + 1));
					}
					else if (map[nx][ny] == s.size) { // 아기상어와 크기가 같은 물고기
						visited[nx][ny] = true;
						q.push(make_pair(make_pair(nx, ny), dist + 1));
					}
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				s.x = i;
				s.y = j;
				s.eat_n = 0;
				s.size = 2;
				s.t = 0;
			}
		}
	}

	while (1) {
		v.clear();
		memset(visited, false, sizeof(visited));

		BFS(s.x, s.y);
		if (v.empty()) {
			cout << s.t;
			break;
		}
		else if (v.size() == 1) { // 먹을 것이 하나 뿐
			map[v[0].x][v[0].y] = 9;
			map[s.x][s.y] = 0;
			s.x = v[0].x;
			s.y = v[0].y;
			s.eat_n++;
			s.t += v[0].dist;

			if (s.eat_n == s.size) {
				s.eat_n = 0;
				s.size++;
			}
		}
		else {
			sort(v.begin(), v.end(), sorting);
			map[v[0].x][v[0].y] = 9;
			map[s.x][s.y] = 0;
			s.x = v[0].x;
			s.y = v[0].y;
			s.eat_n++;
			s.t += v[0].dist;

			if (s.eat_n == s.size) {
				s.eat_n = 0;
				s.size++;
			}
		}
	}
}