Leetcode Python - 200. Number of Islands

Leetcode #200 - Number of Islands

이제 두 번째로 100 문제들을 풀어보겠습니다. 리트코드의 문제 200 ‘Number of Islands’을 파이썬으로 풀어 보도록 하겠습니다.

discuss 참고 포인트는 값이 1일 경우, 상하좌우에 1이 있으면 ‘#’으로 바꾸어줍니다.

전체 코드는 아래와 같습니다.

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count

    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

시간복잡도는

• O(mn) : 모든 노드 방문

공간복잡도는

• O(1) : in place 변경