BOJ (C/C++) 16236번: 아기 상어

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

16236번: 아기 상어

---

풀이

BFS로는 상어가 다음으로 이동할 위치와 해당 위치까지의 거리를 찾았다.

이동 순서를 상, 좌, 우, 하로 설정해서 가장 처음 먹을 수 있는 위치가 문제의 조건을 만족하는 줄 알았지만 아니어서, 우선순위 큐를 사용하여 가장 위쪽, 왼쪽에 위치한 좌표를 찾았다.

 

상어의 크기, 이동 시간 및 종료 조건은 Eat함수로 계산했다.

 

 

주의했던 점

- 상어의 초기 위치의 값은 0으로, 항상 지나갈 수 있음

- 방문 순서를 위, 왼쪽, 오른쪽, 아래로 했더라도 먼저 방문한 위치가 가장 위쪽,왼쪽에 위치하지 않음

- 상어보다 큰 물고기가 있는 경우에는 길을 돌아가므로 단순히 현재, 미래 위치의 차이가 이동에 걸리는 시간이 아님

---

코드

( /* */ 은 방문 순서를 출력해보기 위한 부분)

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

int map[21][21];
int N, shark = 2;
/* int mark = 0, M[21][21] = { 0, }; */

pair<int,pair<int, int>> BFS(int x, int y) {

	bool visited[21][21] = { false, };
	int d[4][2] = { {-1,0},{0,-1},{0,1},{1,0} };
	int nx, ny, cnt;

	// init
	// {움직인 횟수,{다음 x좌표, 다음 y좌표}}, 가장 적은 값을 구하기 위해 오름차순 큐 사용
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Ans;
	queue<pair<int, pair<int, int>>> Q;
	Q.push({ 1,{ x,y } });
	visited[x][y] = true;

	while (!Q.empty()) {
		x = Q.front().second.first, y = Q.front().second.second, cnt = Q.front().first;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			nx = x + d[i][0], ny = y + d[i][1];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny] || map[nx][ny] > shark) continue;

			visited[nx][ny] = true;

			if (map[nx][ny] && map[nx][ny] < shark) Ans.push({ cnt,{ nx,ny } });
			else Q.push({ cnt + 1,{ nx,ny } });
		}
	}

	// 더 이상 움직일 수 없는 경우엔 해당 값이 return됨
	Ans.push({ 1000,{ 100,100 } });

	// 가장 가까운 거리, 가장 위쪽, 가장 왼쪽인 위치
	return Ans.top();
}

int Eat(int x, int y) {
	int move = 0, cnt = 0;
	int nx, ny;
	pair<int, pair<int, int>> loc;

	while (1) {

		// 다음에 갈 위치 찾기
		loc = BFS(x, y);
		nx = loc.second.first, ny = loc.second.second;

		// 더 이상 움직일 수 없으면 함수 종료
		if (loc.first==1000) return move;

		move += loc.first;
		cnt++;
		map[nx][ny] = 0;

		// 먹은 물고기의 수가 상어의 크기와 같다면 상어 크기 증가, 먹은 물고기 수 초기화
		if (cnt == shark) shark++, cnt = 0;

		// 상어를 현재 위치로 이동
		x = nx, y = ny;

		/* M[nx][ny] = ++mark; */
	}
}

int main() {
	int sx, sy;

	// input
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9) sx = i, sy = j, map[i][j] = 0;
		}
	}

	// print
	printf("%d\n", Eat(sx, sy));


	/*for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) printf("%d ", M[i][j]);
		printf("\n");
	}
	*/
	return 0;
}