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

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

16236번: 아기 상어

백준 16236번 아기 상어 문제를 풀었다.

 

상어가 먹이를 찾는 부분은 BFS로 풀었다.

 

내가 사용한 변수는 아래와 같다.

map배열 : 물고기와 아기상어의 위치를 저장

visited 배열 : BFS에서 방문했던 곳을 체크하는 용도

dist 배열 : BFS에서 좌표별로 아기 상어가 움직인 거리를 저장

Fish 구조체 : 물고기의 좌표와 거리를 저장

eatableFish 우선순위큐 : 먹을 수 있는 물고기들을 저장

ans : 아기 상어가 움직인 총 거리

 

문제의 조건은 아래와 같다

1. 먹을 수 있는 물고기가 없으면 아기 상어가 움직인 총 거리를 출력하고 종료

2. 먹을 수 있는 물고기가 1마리면 먹으러 간다

3. 먹을 수 있는 물고기가 2마리 이상이면 가장 가까운 거리에 있는 물고기를 먹으러 간다

3.1 가장 가까운 거리에 있는 물고기가 2마리 이상이면 가장 위에 있는 물고기를 먹으러 간다

3.2 가장 위에 있는 물고기가 2마리 이상이면 가장 왼쪽에 있는 물고기를 먹으러 간다

 

먼저 먹을 수 있는 물고기를 우선 순위 큐에 넣어서 저장했다. 우선 순위 큐의 우선 순위는 아래와 같이 가까이 있는 물고기가 가장 높다. 그 다음은 위에 있는 물고기, 그 다음은 왼쪽에 있는 물고기 순으로 우선 순위를 정했다. BFS를 돌면서 먹을 수 있는 물고기를 eatableFish 우선 순위 큐에 넣으면 자동으로 조건에 맞는 물고기가 top에 위치하게 된다.

struct compare {
	bool operator()(Fish a, Fish b) {
		if (a.dist != b.dist) {
			return a.dist > b.dist;
		}
		else if(a.dist == b.dist) {
			if (a.x == b.x) {
				return a.y > b.y;
			}
			else {
				return a.x > b.x;
			}
		}
	}
};

 

문제 조건에 따라 문제를 풀었다.

1. 문제의 입력을 받아서 아기 상어의 위치, map 배열을 채웠다.

2. 먹을 수 있는 물고기를 찾는 BFS를 수행한다.

3.1 먹을 수 있는 물고기가 없으면 ans 출력 후 종료

3.2 먹을 수 있는 물고기가 있으면 먹으러 간다.

4. 아기 상어를 물고기의 위치로 이동시키고 아기 상어의 크기를 확인한다.

5. BFS를 수행할 때 사용한 배열을 초기화 시킨다.

6. 2~5를 반복한다.

 

주의해야 할 점은 아기 상어가 먹이를 많이 먹어서 크기가 9보다 커졌을 때이다.

아기 상어 본인을 먹을 수 있는 크기이므로, BFS에서 먹을 수 있는 물고기를 찾을 때 아기 상어를 제외해주는 조건을 넣어줘야 한다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#pragma warning(disable:4996)

using namespace std;

struct Node {
	int x;
	int y;
	Node(){}
	Node(int X, int Y) : x(X),y(Y) {}
};

struct Fish {
	int x;
	int y;
	int dist;
	Fish(){}
	Fish(int X, int Y, int D) :x(X), y(Y), dist(D) {}
};

struct compare {
	bool operator()(Fish a, Fish b) {
		if (a.dist != b.dist) {
			return a.dist > b.dist;
		}
		else if(a.dist == b.dist) {
			if (a.x == b.x) {
				return a.y > b.y;
			}
			else {
				return a.x > b.x;
			}
		}
	}
};

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
int N;
int map[20][20];
int visited[20][20];
int dist[20][20];
int ans = 0;
int babySharkSize = 2;
int eatCount = 0;
Node babyShark;
queue<Node> q;
priority_queue<Fish,vector<Fish>,compare> eatableFish;

void sizeCheck() {
	if (eatCount == babySharkSize) {
		eatCount = 0;
		babySharkSize++;
	}
}

Node BFS(Node start) {
	q.push(start);
	visited[start.x][start.y] = 1;
	while (!q.empty()) {
		Node cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			Node next;
			next.x = cur.x + dx[i];
			next.y = cur.y + dy[i];					

			if (next.x >= 0 && next.x < N && next.y >= 0 && next.y < N) {
				if (visited[next.x][next.y] == 0 && map[next.x][next.y] <= babySharkSize) {
					visited[next.x][next.y] = 1;
					dist[next.x][next.y] = dist[cur.x][cur.y] + 1;
					q.push(next);

					if (map[next.x][next.y] != 0 && map[next.x][next.y] != 9 && map[next.x][next.y] < babySharkSize) {
						Fish fish(next.x, next.y, dist[next.x][next.y]);
						eatableFish.push(fish);
					}
				}
			}
		}
	}


	if (eatableFish.size() == 0) {
		return Node(-1, -1);
	}
	else {
		return Node(eatableFish.top().x,eatableFish.top().y);
	}
}

int main() {
	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) {
				babyShark.x = i;
				babyShark.y = j;
			}
		}
	}


	while (1) {
		Node dest = BFS(babyShark);

		// 먹을 수 있는 물고기가 없을 때
		if (dest.x == -1 && dest.y == -1) {
			cout << ans;
			break;
		}
		// 먹을 수 있는 물고기가 있을 때
		else {
			// 아기 상어 이동
			map[babyShark.x][babyShark.y] = 0;
			babyShark.x = dest.x;
			babyShark.y = dest.y;
			map[dest.x][dest.y] = 9;
			ans += dist[dest.x][dest.y];

			// 아기 상어 물고기 먹고 크기 확인
			eatCount++;
			sizeCheck();

			// 변수 초기화
			while (!eatableFish.empty())
				eatableFish.pop();

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					visited[i][j] = 0;
					dist[i][j] = 0;
				}
			}
		}

	}

	return 0;
}