[BOJ][백준 16236] 아기 상어 - C++

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

16236번: 아기 상어

백준 사이트의 16236번 문제, 아기 상어 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

문제 입력 모습

• N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다.
• 한 칸에는 물고기가 최대 1마리 존재한다.
• 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  -> 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  -> 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기      를 먹는다.

• 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

---

1. 문제풀이 아이디어

• 아기 상어의 위치부터 퍼져나가는 BFS알고리즘을 구현한다.
• 만약 자기보다 몸집 큰 물고기 만나면 continue.
• 먹을 수 있는 물고기를 만나면 우선순위에 따라 먹을 물고기를 정해준다.
• 그 위치부터 다시 다음 BFS알고리즘 시작!
• 현재까지 먹은 물고기 수를 계산하여 아기상어 사이즈를 갱신한다.
• 더 이상 먹을 물고기가 없다면 결과 출력

---

2. 코드 핵심 부분

1) BFS 함수의 앞부분, 현재 아기상어 위치에서 퍼져가며 가장 가까운 물고기 찾음.

   BFS 함수중에서 먹을 수 있는 물고기를 찾는 부분만 일단 먼저 보자.

   사실 기본 BFS틀에서 다를건 없고, 0보다 크고 아기상어보다 작은 원소를 만나면 우선순위 큐에 넣어주었다.

// bfs 알고리즘, 현재 아기상어 위치에서 퍼져가며 가장 가까운 물고기 찾음.
void bfs(int sy, int sx) {

	queue<Node> q;
	q.push({ sy, sx });

	int visited[20][20] = { 0 };
	visited[sy][sx] = 1;
	
	int diry[4] = { -1, 0, 1, 0 };
	int dirx[4] = { 0, -1, 0, 1 };
	
	int cnt = 0;

	while (!q.empty()) {
		cnt++;
		int cursize = q.size();

		for (int cycle = 0; cycle < cursize; cycle++) {

			Node now = q.front();
			q.pop();

			for (int i = 0; i < 4; i++) {

				int ny = now.y + diry[i];
				int nx = now.x + dirx[i];

				if (visited[ny][nx] == 1)
					continue;

				if (ny < 0 || nx < 0 || ny >= N || nx >= N)
					continue;

				if (Map[ny][nx] > Size)
					continue;

				if (Map[ny][nx] > 0 && Map[ny][nx] < Size) {
					visited[ny][nx] = 1;
					pq.push({ ny, nx });
					continue;
				}

				visited[ny][nx] = 1;
				q.push({ ny,nx });
			}
		}

 

2) BFS 함수의 뒷부분

   pq는 무조건 빈 배열인 상태로 BFS가 시작되므로, 만약 pq에 원소가 생기면 다음 먹을 수 있는 물고기를 찾은것.

   가장 우선순위의 물고기만 남긴다음에 그 물고기로 나머지 처리를 해주었다.

   그 물고기의 위치가 시작점이 되어 다음 BFS가 작동하게 된다.

		// 한 사이클을 돌았는데 만약 pq가 있으면 먹은것!
		if (!pq.empty()) {
			// 제일 앞에 물고기가 먹어야 하는 물고기
			Node NextFish = pq.top();
			pq.pop();

			while (!pq.empty()) {
				pq.pop();
			}

			pq.push(NextFish);
			ans += cnt;

			Map[NextFish.y][NextFish.x] = 0;
			Eat++;

			if (Eat == Size) {
				Size++;
				Eat = 0;
			}

			break;
		}
	}
}

---

3. 전체 코드

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

using namespace std;

/*
1. 문제읽기
	N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다.
	한 칸에는 물고기가 최대 1마리 존재한다.
	가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
	
	더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
	먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
	먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
		거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
		거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

	몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성
*/

/*
2. 아이디어
	BFS로 이동해서 먹을 수 있는 물고기가 나올때까지 확장한다.
	만약 자기보다 몸집 큰 물고기 만나면 continue.
	현재까지 먹은 물고기수를 계산하여 아기상어 사이즈를 갱신한다.
*/

struct Node {
	int y;
	int x;

	bool operator <  (Node next) const{

		if (y < next.y)
			return false;
		if (y > next.y)
			return true;
		if (x < next.x)
			return false;
		if (x > next.x)
			return true;
		return false;
	}
};

// 필요 인자들
int ans = 0; // 몇 초
int N; // 공간의 크기
int Map[20][20];
int Size = 2; // 현재 아기상어의 사이즈
int Eat; // 현재 먹은 수, 사이즈 커지면 초기화
int sy, sx; // 시작 지점
priority_queue<Node> pq; // 거리가 같은 경우 걸러주기 위해 우선순위 큐

// 값 입력받는 함수
void input() {
	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) {
				sy = i, sx = j;
				pq.push({ sy, sx });
				Map[i][j] = 0;
			}
		}
	}
}

// bfs 알고리즘, 현재 아기상어 위치에서 퍼져가며 가장 가까운 물고기 찾음.
void bfs(int sy, int sx) {

	queue<Node> q;
	q.push({ sy, sx });

	int visited[20][20] = { 0 };
	visited[sy][sx] = 1;
	
	int diry[4] = { -1, 0, 1, 0 };
	int dirx[4] = { 0, -1, 0, 1 };
	
	int cnt = 0;

	while (!q.empty()) {
		cnt++;
		int cursize = q.size();

		for (int cycle = 0; cycle < cursize; cycle++) {

			Node now = q.front();
			q.pop();

			for (int i = 0; i < 4; i++) {

				int ny = now.y + diry[i];
				int nx = now.x + dirx[i];

				if (visited[ny][nx] == 1)
					continue;

				if (ny < 0 || nx < 0 || ny >= N || nx >= N)
					continue;

				if (Map[ny][nx] > Size)
					continue;

				if (Map[ny][nx] > 0 && Map[ny][nx] < Size) {
					visited[ny][nx] = 1;
					pq.push({ ny, nx });
					continue;
				}

				visited[ny][nx] = 1;
				q.push({ ny,nx });
			}
		}

		// 한 사이클을 돌았는데 만약 pq가 있으면 먹은것!
		if (!pq.empty()) {
			// 제일 앞에 물고기가 먹어야 하는 물고기
			Node NextFish = pq.top();
			pq.pop();

			while (!pq.empty()) {
				pq.pop();
			}

			pq.push(NextFish);
			ans += cnt;

			Map[NextFish.y][NextFish.x] = 0;
			Eat++;

			if (Eat == Size) {
				Size++;
				Eat = 0;
			}

			break;
		}
	}
}

// 메인함수
int main() {

	// input
	input();

	// solve -> bfs돌리면 된다. 언제까지? 먹을 물고기가 없을때까지
	// -> 물고기를 먹으면 그 지점을 다시 시작점으로 bfs
	while (!pq.empty()) {
		Node now = pq.top();
		pq.pop();
		bfs(now.y, now.x);
	}

	// output
	cout << ans;

	return 0;
}

---

4. 문제 풀이를 마치며..

백준 채점 결과

완전 탐색중에 퍼져나가며 최소거리의 물고기를 찾는 것이기에 BFS알고리즘을 사용해야하고,

아기상어의 위치가 계속 바뀌기 때문에 그 자리를 갱신하며 다시 BFS를 돌려야 한다는 아이디어가 핵심인 문제였다.

 

BFS알고리즘 틀을 못외워서 항상 메모장 켜고 보고 했던것이 엊그제 같은데

이제는 DFS만큼이나 능숙하게 작성할 수 있어졌다.

 

이런 성장의 즐거움을 느낄 수 있었던 좋은 문제였던 반면,

우선순위 큐를 굳이 사용해야 했나 하는 아쉬움은 남는다.

 

근데 실행시간이 넉넉했으니 뭐..

잘 풀었다고 생각한다.