[C++][백준] - 아기상어 (16236번)

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

16236번: 아기 상어

🔔 문제 : 

너무 너무 고민을 많이한 문제였습니다. ㅠㅠ.. 문제를 정말 잘 이해해야지 풀 수 있습니다.

 

(2<=N<=20) 인 N*N 인 공간에, (아기상어 = 9)아기상어 1마리가 있습니다.

또한 ( 1<= 물고기 <=6) 크기의 물고기들도 살고 있습니다.

 

예를들면 이런 식입니다.

아기상어는 9이고, 나머지 숫자들은 물고기입니다.

 

아기상어가 돌아다니면서 먹이를 먹습니다. 단, 조건은

 

1. 아기상어는 처음 몸집의 크기가 2입니다. 아기상어는 먹이를 먹을 수록 몸집이 커집니다( 단, 자기 몸집 크기갯수만큼 먹어야합니다. 예를들면 초기몸집이 2이니, 먹이를 2개 먹어야지 몸집 3이 됩니다.)

2. 아기상어는 자기 몸집보다 작은 물고기를 먹을 수 있습니다.

3. 아기상어는 자기 몸집보다 큰 물고기는 지나갈 수 없습니다.(단, 자기 몸집과 같은 물고기는 지나갈 수 있습니다.)

 

4. 아기상어는 가장 가까운 먹이부터 먹습니다.

 

5. 가장 가까운 먹이가 여러마리라면, 맨 위의 먹이부터 먹습니다. 먹이의 행이 같다면, 왼쪽에 있는 먹이부터 먹습니다.

 

6. 아기상어가 한칸씩 움직일때마다 시간 1초씩 흐릅니다.

7. 아기상어는 먹을 먹이가 없을 때 까지 먹이를 찾아 움직입니다.

 

 

최종적으로 아기상어가 먹이를 다 찾고 움직인 시간을 찾아 출력하는 문제입니다.

---

🔔 Kick Point :

아기상어가 어떤 먹이부터 먹는지 문제를 이해해야지 쉽게 풀 수 있을 듯 합니다. (저는 이 부분에서 이해를 못해서 시간이 너무 걸렸어요)

 

가운데에 아기상어가 있고, 1인 크기의 먹이가 저렇게 있습니다.

 

모두 아기상어에게는 거리가 가까운 먹이이죠,

 

여기서 아기상어는 자기보다 위에있는 노란박스를 있는 먹이를 먼저 찾습니다.

그 다음에는 자기보다 왼쪽에 있는 빨간색 박스의 먹이를 찾습니다.

 

이러한 순서로 아기상어가 먹이를 발견하면 그 먹이를 먹으로 갑니다.

 

 

이 먹이를 발견하는 방법을 BFS()를 통해 구해야합니다.

Queue에 집어 넣은 후, 

 

1. 가장 가까운 먹이를 우선으로!

 

2. 가장 가까운 먹이가 여러마리라면, 맨위를 우선으로.

 

3. 먹이들의 행이 같다면, 맨 왼쪽의 먹이를 우선으로! 먹습니다.

 

 

루프 순서는 이러합니다.

1. 아기상어의 위치와 몸집을 저장합니다.

2. BFS()를 통하여 아기상어가 먹을 먹이를 정합니다.

3. 먹고, 아기상어의 위치와 몸집을 갱신합니다.

4. 1~3을 반복하다가, 먹을 먹이가 없으면 시간을 출력합니다.

 

 

BFS()를 실행할때, feedY, feedX 라는 먹이의 y,x좌표를 지속적으로 갱신하여, 먹이를 찾아내어야합니다.

---

🔔 Code :

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

// variable
tuple<int, int, int> shark; // y, x, 상어크기
queue<tuple<int, int, int>> q; // BFS를 위한 Q (y, x, 이동거리)
int n;
int map[22][22];
bool isVisited[22][22];
int dy[4] = { -1, 0, 0, 1 };
int dx[4] = { 0, -1, 1, 0 };
int MAX = 0, curFeed = 0, feedY = -1, feedX = -1;

void clear() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			isVisited[i][j] = false;
		}
	}
	feedY = -1;
	feedX = -1;
}

// 가까운 먹이 찾기 (거리가 같으면 맨 위(같은 행이면 그 행), 그 중 맨 왼쪽)
int BFS() {
	int Min = 123123; // 최소거리
	int y = get<0>(shark); int x = get<1>(shark); 
	int sharkSize = get<2>(shark);
	q.push({ y, x, 0});
	map[y][x] = 0;
	isVisited[y][x] = true;

	while (!q.empty()) {
		int _y = get<0>(q.front()); int _x = get<1>(q.front()); // y좌표, x좌표
		int _cnt = get<2>(q.front()); // 물고기까지의 거리
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = _y + dy[i];
			int nx = _x + dx[i];

			// 지도밖으로 넘어갔을 경우 넘어갑니다.
			if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
			// 이미 방문한 물고기이고, 상어보다 큰 물고기인경우 넘어갑니다.
			if (isVisited[ny][nx] || map[ny][nx] > sharkSize) continue;

			// 먹을 수 있는 물고기인 경우
			if (map[ny][nx] < sharkSize && map[ny][nx] != 0) {
				// 최소 거리인 경우, 먹이좌표에 무조건 담습니다.
				if (Min > (_cnt + 1)) {
					Min = _cnt + 1;
					feedY = ny;
					feedX = nx;
				}
				// 최소 거리가 여러마리이고, 우선순위에 따르는 경우
				else if (Min == (_cnt + 1)) {
					// 다른 행인 경우, 맨위를 기준으로 합니다.
					if (feedY > ny) {
						feedY = ny;
						feedX = nx;
					}
					// 같은 행인경우, 왼쪽를 기준으로 합니다.
					else if (feedY == ny) {
						// 왼쪽을 기준으로
						if (feedX > nx) {
							feedY = ny;
							feedX = nx;
						}
					}
				}
			}
			// 이동한 곳은 넣어두고, 다시는 못찾게 만듭니다.
			q.push({ ny, nx, _cnt + 1 });
			isVisited[ny][nx] = true;
		}
	}

	// 먹이를 찾은 아기상어
	if (Min != 123123) {
		return Min;
	}
	// 먹이를 찾지 못한 아기상어, 엄마를 부릅니다 엄마~
	else {
		return 0;
	}

}


int main() {

	// Input
	cin >> n;
	for (int i = 0; i < n * n; i++) {
		int x = i % n; x++;
		int y = i / n; y++;

		cin >> map[y][x];
		if (map[y][x] == 9) shark = { y, x, 2 };
	}

	// Algorithm
	while (true) {
		clear();
		int t = BFS();
		if (t == 0) break;
		else {
			// 먹이를 찾은 아기상어
			MAX += t;
			map[feedY][feedX] = 0;

			// 아기상어 몸집 및 위치 갱신
			curFeed++;
			if (curFeed == get<2>(shark)) {
				shark = { feedY, feedX, get<2>(shark) + 1 };
				curFeed = 0;
			}
			else {
				shark = { feedY, feedX, get<2>(shark) };
			}
		}
	}

	// Output
	cout << MAX;
}

---