number of islands

number of islands

• m x n 의 2차원 그리드
• "1" 은 land,"0"은 water를 의미
• 그리드 공간에서 islands(연결된 "1")의 개수 반환

solution

• dfs를 이용
• m x n 의 각 점들중 "1"인점 을 출발점으로 해서 도달가능한 모든점을 방문(dfs) 하고, 섬의개수 1증가 시키기
• 한번 방문한 점은 "0" 으로 표시
• grid 상에서 한 점(i,j)의 방문가능한 이웃한 점은 상하좌우에 위치하면서, 그리드 범위 이내이고 값이 "1" 인점

code

class Solution(object):


    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """

        # m , n , dirs 초기화
        m, n = len(grid), len(grid[0])
        dirs = ((1,0),(0,1),(-1,0),(0,-1))

        def _dfs(i,j):
            grid[i][j]="0"
            for _i,_j in dirs:
                x,y = i+_i, j+_j
                if 0 <= x < m and 0 <= y < n and grid[x][y]=="1":
                    _dfs(x,y)

        num_islands = 0
        for i in range(m):
            for j in range(n):
                # visit only land
                if grid[i][j] == "1":
                    _dfs(i,j)
                    num_islands+=1
        return num_islands