[BOJ] 16236 : 아기 상어 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. 현재 상어 위치에서 BFS 탐색을 진행해 갈 수 있는 모든 곳을 탐색하며 먹을 수 있는 물고기의 거리, 좌표를 담는다.

2.

- 먹을 수 있는 물고기가 없다면 종료

- 있다면 가장 가까우면서 상단에 있으면서 왼쪽에 있는 즉 거리가 작고, x 좌표가 작고, y 좌표가 작은 순으로 sort 한 후 가장 앞에 있는 물고기를 먹으면 된다.

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

using namespace std;

int N, map[20][20], sX, sY, sS = 2, sC = 0, time = 0;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };

void Init(void) {
	while(1){
		if (sS == sC){
			sC = 0, sS++;
		}
		// 지금 상어가 먹을 수 있는 물고기의 거리와 좌표를 담자.
		vector<pair<int, pair<int, int>>> fish;

		// BFS 탐색을 하자.
		bool checkMap[20][20] = {};
		queue<pair<pair<int, int>, int >> q;
		checkMap[sX][sY] = true;
		q.push(make_pair(make_pair(sX, sY), 0));
		while (!q.empty()) {
			pair<pair<int, int>, int> temp = q.front();
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nextX = temp.first.first + dx[i], nextY = temp.first.second + dy[i];
				if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) { // map을 벗어나지않고
					if (checkMap[nextX][nextY] == false && map[nextX][nextY] <= sS) { // 처음가보는데 지나갈 수 있는곳
						checkMap[nextX][nextY] = true;
						q.push(make_pair(make_pair(nextX, nextY), temp.second + 1));
						if (map[nextX][nextY] != 0 && map[nextX][nextY] < sS) { // 먹을 수 있는 물고기
							fish.push_back(make_pair(temp.second + 1, make_pair(nextX, nextY)));
						}
					}
				}
			}
		}
		if (fish.empty())
			break;
		// 가까운 거리가 왼쪽 상단부터 sort된다.
		sort(fish.begin(), fish.end());
		// 첫 번째 물고기를 먹으면 된다.
		time += fish[0].first;
		sX = fish[0].second.first, sY = fish[0].second.second, sC++;
		map[sX][sY] = 0;
	}	
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	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) {
				sX = i, sY = j;
				map[sX][sY] = 0;
			}
		}
	Init();
	cout << time;
	return 0;
}

---