1162. As Far from Land as Possible

1162. As Far from Land as Possible

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

문제

풀이(BFS)

에서 (0, 0) = 1인 것을 알 수 있다. 여기서 자명한 사실은 1에서 상,하,좌,우는 1로 가장 짧은 거리인 것을 알 수 있다.

자료구조 큐에 (0,1) ,(1, 0)을 넣고 마찬가지로 (0, 1)에서 상하좌우, (1, 0)에서 상하좌우 값을 구한다.

이런식으로 자료구조 큐에 방문하지 않은 grid값을 저장하고 +1씩 늘려나간다.

만약 육지가 여러개 있을 때에는 어떻게 될까?

자료구조 큐에 (0, 0), (1,1), (3,4)값을 저장한다.

자료구조 큐에서 (0, 0)상하좌우, (1,1) 상하좌우 (3,4)상하좌우 값을 1증가시킨다. 그 후 상하좌우 값 좌표를 큐에 저장한다.
(1, 0), (0, 1), (1, 2), (1, 3), (2, 1), (2, 2)값이 저장 될 것이다. 이제 해당 좌표에서 상하좌우 값을 1 증가시키면 다음과 같다.

이것을 코드로 나타내면

결과(BFS)