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

서론

BFS문제.

아이디어

현재 위치에서 가장 가까운 물고기를 찾아야 하므로 BFS를 실행한다. 조건에 맞게 물고기를 먹고 BFS를 빠져나온 후, 물고기를 먹은 위치에서 BFS를 다시 실행하기를 반복한다.

가장 가까운 물고기가 여러마리일 경우, 가장 위의 물고기를 먹고 가장 위의 물고기가 여러마리면 가장 왼쪽의 물고기를 먹어야한다. 우선 BFS를 실행했을때 물고기를 먹고 바로 BFS를 빠져나오는게 아닌 동일한 거리의 물고기는 모두 벡터에 넣고 빠져나온다. 이를 위해 1초 후 이동할 것들은 제외한 큐의 사이즈만큼만 반복하고 BFS를 빠져나온다.

while(!q.empty()){

qSize = q.size();

while(qSize--){

물고기를 만나면 통(벡터)에 넣음

}

if(통에 물고기가 있음) {

여러마리 물고기 중 뭘 먹을까 선택

break;

}

위와 같이 만들면 내부 while은 현재 새롭게 큐에 넣은것은 제외한 1초 전에 큐에 넣은 칸들만 확인하게 된다. 또한 내부 while은 break문이 없기 때문에 물고기를 먹고 나서도 또 먹을게 있는지 확인하고 빠져나온다.

물고기를 만날때마다 물고기의 좌표를 벡터에 넣어준다. 넣을 수 있는 물고기를 다 넣었으면 벡터를 y, x순으로 오름차순 정렬한다. 그럼 벡터의 front는 가장 위의 가장 왼쪽 물고기 위치다.

총 소요시간은 방문 확인용 visited 배열을 만들고 상어가 새로운 칸을 방문할때마다 vistied 이전칸의 값에서 +1 해주면 물고기를 먹을때의 visited 값은 BFS를 한번 돌릴때 상어가 이동한 소요 시간이다. BFS를 실행할때마다 소요 시간을 계속 더해주면 된다.

구현

//c++

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

int map[21][21];
int visited[21][21];
int dy[4] = { -1,0,0,1 };
int dx[4] = { 0,-1,1,0 };
int size = 2;
int n;
int sharkY;
int sharkX;
int ate;
int time;
bool ateFlag = false;

void createMap() {
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			std::cin >> map[i][j];
			if (map[i][j] == 9) {
				sharkY = i;
				sharkX = j;
				map[i][j] = 0;
			}
		}
	}
}

void bfs() {
	std::queue<std::pair<int, int>>q;
	std::vector<std::pair<int, int>>v;
	q.push({ sharkY, sharkX });
	visited[sharkY][sharkX] = 1;
	ateFlag = false;

	while (!q.empty()) {
		int qSize = q.size();
		while (qSize--) {
			int y = q.front().first;
			int x = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny >= 0 && nx >= 0 && ny < n && nx < n && visited[ny][nx] == 0) {
					if (map[ny][nx] == 0 || map[ny][nx] == size) { // 상어가 이동 가능
						q.push({ ny, nx });
						visited[ny][nx] = visited[y][x] + 1;
					}
					else if (map[ny][nx] < size) { // 물고기를 만남
						v.push_back({ ny, nx });
						visited[ny][nx] = visited[y][x] + 1;
					}
				}
			}
		}
		if (v.size() >= 1) { // 먹을 수 있는 물고기가 여러마리일 때
			std::sort(v.begin(), v.end());
			map[v[0].first][v[0].second] = 0;
			ateFlag = true;
			sharkY = v[0].first;
			sharkX = v[0].second;
			ate++;
			time += visited[v[0].first][v[0].second] - 1;
			break;
		}
	}
}

int main() {
	createMap();
	while (1) {
		bfs();

		memset(visited, 0, sizeof(visited));
		if (ateFlag == false) break;
		else if (ate == size) {
			size++;
			ate = 0;
		}
	}
	std::cout << time;
}