[BOJ][16236] 아기 상어

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

---

거리가 가장 가까운 먹을 수 있는 물고기를 찾되 조건에 해당하는 물고기가 여러마리라면 가장 위, 가장 왼쪽에 있는 물고기를 먹으러 간다. 

가장 가까운 먹을 수 있는 물고기를 찾아야하므로 BFS(너비우선탐색)을 하는데 가장 위, 가장 왼쪽에 있는 물고기를 찾아야 하므로 큐가 아닌 우선 순위 큐를 사용했다.

우선 순위 큐에 (현재 상어 위치와 이동하고자 하는 좌표간 거리(dist), (이동하고자 하는 좌표(x, y))) 를 저장한다.

해당 큐에서 좌표간 거리가 가장 짧고, 이동하고자 하는 좌표(x, y)를 x가 작을 수록, y가 작을수록 높은 우선순위를 가진다.

우선 순위 : dist 오름차순 -> x 오름차순 -> y 오름차순

 

상어가 지나갈 수 있는(or 먹을 수 있는 물고기가 있는) 칸들을 이동하면서 해당 큐에 거리, 좌표를 넣어준다.

지나갈 수 있는 칸들은 상어 크기보다 칸의 수가 작거나 같은 경우이다.

만약 현재 탐색 중인 dist, x, y가 arr[x][y]가 상어 크기보다 작고 0보다 크다면 해당 칸에 있는 물고기를 상어가 잡아먹는다. 우선순위 큐 조건에 의해 탐색 중 가장 먼저 해당 조건을 만족하는 칸이 다음 상어가 먹는 칸이 되므로 탐색을 종료한다.

 

위 bfs로 현재 위치(let, (x,y))에서 이동할 다음 칸(let, (nx, ny))과 해당 칸으로 이동하는데 까지의 거리(let, dist)을 찾았다면 정답에 dist를 더하고 현재 위치를 nx, ny로 갱신한다. (nx, ny) 칸의 물고기는 상어가 잡아먹으므로 arr[nx][ny]는 0으로 갱신한다. 상어 크기 갱신을 위해 이때까지 잡아먹은 물고기 수를 저장하는 변수(let, eatedFishes)를 하나 두고 상어가 이동할 때 해당 변수를 +1 해준다. 만약 이 변수가 상어 크기와 같아진다면 상어 크기를 1증가시키고 해당 변수는 0으로 갱신한다.

만약 이동할 다음 칸이 없다면 탐색을 종료하고 정답을 출력한다.

 

최대 N*N 칸을 이동할 수 있고 한 칸을 이동하는데 한 번의 BFS를 돌린다. BFS를 돌릴 때 우선순위큐를 사용하고 큐에는 최대 총 N*N 개의 요소가 들어가므로 한 번의 BFS는 O(N*N log(N*N))의 시간복잡도를 가진다.

따라서 총 시간복잡도는 O(N*N * N*N log(N*N)).

보기 쉽게 N*N(칸의 총 개수)를 M으로 본다면 O(M^2 log(M^2))가 된다.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/BOJ/16236.%20%EC%95%84%EA%B8%B0%20%EC%83%81%EC%96%B4.cpp