200. Number of Islands (Array, Depth-First Search, Breadth-First Search, Union Find, Matrix)

링크 - https://leetcode.com/problems/number-of-islands/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 BFS를 통해 이 문제를 풀 수 있다. 매번 "1"이 나올때마다 우리는 BFS를 통해 근접 "1"들을 찾아나가며 섬을 찾는다. 

중요한 점은 BFS의 Space complecity가 O(min(M, N))이라는 점이다. 왜냐하면 BFS를 위한 queue의 사이즈는 min(M, N)까지 최대로 증가하기 때문이다.

Code

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ans = 0
        rows = len(grid)
        cols = len(grid[0])

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == "1":
                    ans += 1
                    queue = deque()
                    queue.append((row, col))
                    grid[row][col] == "X"

                    while queue:
                        r, c = queue.popleft()
                        print(r, c)

                        if r > 0 and grid[r-1][c] == "1":
                            grid[r-1][c] = "X"
                            queue.append((r-1, c))
                        if c > 0 and grid[r][c-1] == "1":
                            grid[r][c-1] = "X"
                            queue.append((r, c-1))
                        if r < rows - 1 and grid[r+1][c] == "1":
                            grid[r+1][c] = "X"
                            queue.append((r+1, c))
                        if c < cols - 1 and grid[r][c+1] == "1":
                            grid[r][c+1] = "X"
                            queue.append((r, c+1))

        return ans

Complexity

여기서 M은 Row의 개수이고, N은 Col의 개수이다.

Time Complexity: O(M * N)

Space Complexity: O(min(M, N))