[leetcode] 1162. As Far from Land as Possible

문제 : https://leetcode.com/problems/as-far-from-land-as-possible/

---

BFS로 풀었다.

먼저 grid를 모두 돌면서 land인 부분을 찾아서 queue에 x, y를 저장한다.

 

queue가 빌 때 까지 돌면서 distance를 갱신한다.

탐색 시 x, y 위치에 현재까지 저장된 land와의 거리 + 1로 상하좌우 cell에 갱신가능한지 보아야 한다. 

이 때 distance는 가장 가까운 land와의 거리이므로 거리가 아직 세팅되지 않은 경우(아직 어떠한 land와도 거리가 갱신되지 않음)와 거리가 세팅되었다면 이미 세팅된 거리보다 가까운 경우에만 갱신된다.

거리가 갱신된 경우 다시 queue에 현재 위치를 넣어준다.

 

queue가 비었으면 cell의 거리 갱신이 끝난 경우이다.

끝났을 때 다시 한번 grid를 돌면서 최대 거리를 찾아주고 이를 리턴한다.

최대 거리가 0인 경우는 -1을 리턴해야한다.

 

시간복잡도는 grid의 전체 크기를 N, land의 개수를 M이라 했을 때, O(NM)이다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1162.%20As%20Far%20from%20Land%20as%20Possible.cpp