알고리즘 문제/Leetcode
[Leetcode] 1254. Number of Closed Islands
햄과함께
2023. 4. 6. 20:42
320x100
문제 : https://leetcode.com/problems/number-of-closed-islands/description/
0(육지)과 1(물)로 이루어진 2차원 그리드가 주어집니다. 섬은 4방향으로 연결된 0으로 이루어진 최대 그룹이며, 폐쇄된 섬은 1로 둘러싸인 섬입니다.
폐쇄된 섬의 수를 반환하세요.
섬은 물로 완벽하게 둘러쌓여야 하므로 배열의 가장자리와 맞닿아 있는 육지는 섬으로 보지 않습니다.
따라서, 먼저 가장자리부터 탐색하면서 DFS 혹은 BFS로 가장자리 땅이 육지인 경우 연결된 육지들을 전부 물로 바꿔주는 사전작업을 해줍니다.
이 후, 땅들을 다시 탐색하면서 탐색 중인 땅이 육지인 경우 정답을 1 추가한 뒤, 마찬가지로 DFS/BFS로 연결된 육지들을 모두 물로 바꿔줘서 중복 정답이 되는 것을 방지합니다.
모든 땅을 탐색했을 때 정답을 구할 수 있습니다.
시간복잡도는 O(NM).
320x100