[Leetcode] 1254. Number of Closed Islands

문제 : https://leetcode.com/problems/number-of-closed-islands/description/

---

0(육지)과 1(물)로 이루어진 2차원 그리드가 주어집니다. 섬은 4방향으로 연결된 0으로 이루어진 최대 그룹이며, 폐쇄된 섬은 1로 둘러싸인 섬입니다.

폐쇄된 섬의 수를 반환하세요.

---

섬은 물로 완벽하게 둘러쌓여야 하므로 배열의 가장자리와 맞닿아 있는 육지는 섬으로 보지 않습니다.

따라서, 먼저 가장자리부터 탐색하면서 DFS 혹은 BFS로 가장자리 땅이 육지인 경우 연결된 육지들을 전부 물로 바꿔주는 사전작업을 해줍니다.

이 후, 땅들을 다시 탐색하면서 탐색 중인 땅이 육지인 경우 정답을 1 추가한 뒤, 마찬가지로 DFS/BFS로 연결된 육지들을 모두 물로 바꿔줘서 중복 정답이 되는 것을 방지합니다.

모든 땅을 탐색했을 때 정답을 구할 수 있습니다.

 

시간복잡도는 O(NM).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1254.%20Number%20of%20Closed%20Islands.cpp