백준 16236 - 아기 상어

문제링크

• 백준 16236

문제설명

• NxN 크기의 공간에 물고기 M마리와 아기 상어 1마리가 존재한다. (0 <= M <N*N-1)
• 물고기와 아기상어는 모두 크기를 가지고 있는데, 두 개체의 크기 간의 관계는 다음과 같다.
  • 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다.
  • 자신의 크기보다 작은 물고기만 먹을 수 있다. 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
• 아기 상어의 이동 로직은 다음과 같다.
  • 1초에 상하좌우로 인접한 한칸씩 이동할 수 있다.
  • 먹을 수 있는 물고기가 있다면, 그 물고리를 먹으러 가야하고 규칙은 다음과 같다.
    • 거리가 가장 가까운 물고기를 먹어야 한다. 거리는 물고기까지의 최단 거리로 정의한다.
    • 거리가 같은 물고기가 여러마리라면, 가장 위쪽에 있는 물고기를 먹고, 위쪽에 있는 물고기가 여러마리라면 가장 왼쪽에 물고기를 먹는다.
  • 자신의 크기와 같은 개수만큼 물고리를 먹으면 크기가 1씩 커진다. 예를 들어, 아기 상어 크기가 2인 상태에서 2마리를 먹으면 크기가 3이 된다. 크기가 3인 상태에서 3마리를 더 먹으면 4가 된다.

필요한 지식

• BFS 를 활용하여 아기 상어에서 접근할 수 있는 모든 물고기까지의 최단 거리를 미리 계산해두어야 한다.
  • 시작점에서 모든 정점까지 최단 거리를 계산하는 대표적인 알고리즘으로는 BFS, 다익스트라 등이 있다.
  • BFS 는 모든 간선의 가중치가 1로 같을때 최단 경로를 찾아준다.
• 먹을 수 있는 물고기를 찾으면 거리가 최소이고, 가장 위쪽, 가장 왼쪽에 위치한 물고기를 타겟으로 갱신할 수 있어야 한다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;

int N;
int board[20][20];
int visited[20][20] = { false, };
int dist[20][20]; // 아기 상어가 접근할 수 있는 물고기와의 거리 정보
int minDist = 1000, minX = 20, minY = 20;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void init() {
	memset(visited, false, sizeof(visited));
	memset(dist, 0, sizeof(dist));
	minDist = 1000, minX = 20, minY = 20;
}

void Bfs(pair<int, int> babyShark, int size) {
	queue<pair<int, int>> q;
	q.push(babyShark);
	visited[babyShark.first][babyShark.second] = true;

	while (!q.empty()) {
		pair<int, int> cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nextX = cpos.first + dx[dir];
			int nextY = cpos.second + dy[dir];
			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
			if (board[nextX][nextY] > size) continue;
			if (visited[nextX][nextY]) continue;
			visited[nextX][nextY] = true;
			q.push(make_pair(nextX, nextY));
			dist[nextX][nextY] = dist[cpos.first][cpos.second] + 1;

			// 먹을 수 있는 물고기
			if (board[nextX][nextY] > 0 && board[nextX][nextY] < size) {
				if (dist[nextX][nextY] < minDist) {
					minDist = dist[nextX][nextY];
					minX = nextX, minY = nextY;
				}
				else if (dist[nextX][nextY] == minDist) {
					if (nextX < minX) { // 더 위쪽에 있는 경우
						minX = nextX, minY = nextY;
					}
					else if (nextX == minX) {
						if (nextY < minY) // 더 왼쪽에 있는 경우
							minX = nextX, minY = nextY;
					}
				}
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	scanf("%d", &N);
	pair<int, int> babyShark;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			scanf("%d", &board[r][c]);
			if (board[r][c] == 9) 
				babyShark = { r,c };
		}
	}

	int ans = 0;
	int size = 2;
	int eatCnt = 0;
	while (true) {
		init();

		Bfs(babyShark, size);
		if (minDist == 1000) break;
		ans += minDist;
		eatCnt++;
		if (eatCnt == size) {
			eatCnt = 0;
			size++;
		}
		board[babyShark.first][babyShark.second] = 0;
		board[minX][minY] = 0;
		babyShark = { minX, minY };
		board[babyShark.first][babyShark.second] = 9;
	}

	printf("%d\n", ans);
	return 0;
}