백준 16236 아기 상어 (c++) : 피너클

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

16236번: 아기 상어

bfs, 구현문제다.

미친듯이 귀찮은 문제다.

int n;
int map[21][21];
int shark_y, shark_x, shark_body = 2, shark_eat = 0;
int next_y, next_x, next_dist;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };
bool visited[21][21];
vector<pair<int, int>> fish;

사용할 변수들이다.

cin >> n;
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		cin >> map[i][j];
		if (map[i][j] == 9) {
			map[i][j] = 0;
			shark_y = i, shark_x = j;
		}
		else if (1 <= map[i][j] && map[i][j] <= 8) {
			fish.push_back({ i, j });
		}
	}
}

값들을 입력받을때 9라면 상어의 위치를 조정해주고 1에서 8 사이의 숫자라면 물고기 위치를 추가해준다.

int time = 0;
while (1) {
	next_y = next_x = next_dist = 987654321;
	find_fish();
	if (next_dist == 987654321) {
		break;
	}

time은 걸린 시간이다.

next_y, nex_x, next_dist는 각각 아기상어가 움직이고 난 다음 위치, 다음 위치까지의 거리를 의미한다.

find_fish()를 실행하면 next_y, nex_x, next_dist들이 업데이트 된다.

만약 next_dist가 여전히 987654321라면 더이상 먹을 수 있는 물고기가 없다는 뜻이다. while문에서 바로 나온다.

	time += next_dist;
	shark_eat++;
	map[next_y][next_x] = 0;
	if (shark_eat == shark_body) {
		shark_eat = 0;
		shark_body++;
	}
	shark_y = next_y;
	shark_x = next_x;
}
cout << time << endl;

time에 거리를 더해주고 shark_eat++를 해준다.

만약 상어가 먹은 양이 상어의 몸 크기와 같다면 shark_eat = 0, shark_body++를 해준다.

그후 상어의 위치를 먹은 물고기의 위치로 바꿔준다.

while문을 나가면 time을 출력한다.

void find_fish() {
	queue<pair<int, pair<int, int>>> pq;
	pq.push({ 0,{ shark_y, shark_x } });
	memset(visited, false, sizeof(visited));
	visited[shark_y][shark_x] = true;

find_fish다.

pq에는 {이동한 거리, 현재 위치}가 들어간다.

pq에 0과 현재 위치를 넣어준뒤 visited를 초기화 하고 상어의 처음 위치는 true로 바꾼다.

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
			
		if (1 <= ny && ny <= n && 1 <= nx && nx <= n) {
			if (!visited[ny][nx]) {

이동할수 있는 4방향을 확인한다. 만약 범위안에 있고 방문하지 않은 좌표라면

				visited[ny][nx] = true;
				if (map[ny][nx] == 0 || map[ny][nx] == shark_body) {
					pq.push({ dist + 1,{ ny, nx } });
				}

방문으로 표시해준다.

만약 다음 위치가 0이거나 현재 위치에 있는 물고기의 크기가 상어의 크기와 같다면

pq에 {현재 까지 이동한 거리 + 1, 다음 좌표}를 추가한다.

				else if (map[ny][nx] != 0 && map[ny][nx] < shark_body) {
					if (dist + 1 < next_dist) {
						next_y = ny;
						next_x = nx;
						next_dist = dist + 1;
					}
					else if (dist + 1 == next_dist) {
						if (ny < next_y) {
							next_y = ny;
							next_x = nx;
						}
						else if (ny == next_y && nx < next_x) {
							next_y = ny;
							next_x = nx;
						}
					}
					pq.push({ dist + 1, {ny, nx} });
				}

만약 다음 좌표가 0이 아니고 먹을 수 있는 물고기라면 먹을건지 확인해야한다.

만약 다음 좌표까지 이동하는 거리가 next_dist보다 작다면 바로 모든 값을 업데이트한다.

만약 다음 좌표까지 이동하는 거리가 next_dist와 같다면 문제에 나와있는 조건들을 확인한다.

보다 더 위쪽에 있거나 보다 더 왼쪽에 있다면 모든 값을 업데이트 한다.

마지막으로 pq에 값을 집어넣는다.

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

using namespace std;

int n;
int map[21][21];
int shark_y, shark_x, shark_body = 2, shark_eat = 0;
int next_y, next_x, next_dist;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };
bool visited[21][21];
vector<pair<int, int>> fish;

void find_fish() {
	queue<pair<int, pair<int, int>>> pq;
	pq.push({ 0,{ shark_y, shark_x } });
	memset(visited, false, sizeof(visited));
	visited[shark_y][shark_x] = true;

	while (!pq.empty()) {
		int y = pq.front().second.first;
		int x = pq.front().second.second;
		int dist = pq.front().first;
		pq.pop();

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

			if (1 <= ny && ny <= n && 1 <= nx && nx <= n) {
				if (!visited[ny][nx]) {
					visited[ny][nx] = true;
					if (map[ny][nx] == 0 || map[ny][nx] == shark_body) {
						pq.push({ dist + 1,{ ny, nx } });
					}
					else if (map[ny][nx] != 0 && map[ny][nx] < shark_body) {
						if (dist + 1 < next_dist) {
							next_y = ny;
							next_x = nx;
							next_dist = dist + 1;
						}
						else if (dist + 1 == next_dist) {
							if (ny < next_y) {
								next_y = ny;
								next_x = nx;
							}
							else if (ny == next_y && nx < next_x) {
								next_y = ny;
								next_x = nx;
							}
						}
						pq.push({ dist + 1, {ny, nx} });
					}
				}
			}
		}
	}
	return;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				map[i][j] = 0;
				shark_y = i, shark_x = j;
			}
			else if (1 <= map[i][j] && map[i][j] <= 8) {
				fish.push_back({ i, j });
			}
		}
	}

	int time = 0;
	while (1) {
		next_y = next_x = next_dist = 987654321;
		find_fish();
		//cout << next_y << ' ' << next_x << ' ' << next_dist << endl;
		if (next_dist == 987654321) {
			break;
		}

		time += next_dist;
		shark_eat++;
		map[next_y][next_x] = 0;
		if (shark_eat == shark_body) {
			shark_eat = 0;
			shark_body++;
		}
		shark_y = next_y;
		shark_x = next_x;
	}
	cout << time << endl;
}

전체코드다.