Number of Islands

행렬에 있는 1의 뭉치를 세는 문제. 너비 우선 탐색을 쓰면 쉽게 해결된다

https://leetcode.com/problems/number-of-islands/

 

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited = set()
        count = 0
        rowCount = len( grid )
        
        if not rowCount:
            return 0
        
        columnCount = len( grid[ 0 ] )
        
        if not columnCount:
            return 0
        
        for row, rowList in enumerate( grid ):
            for column, v in enumerate( rowList ):
                if v == '1':
                    if self.__paint( grid, row, column, visited, rowCount, columnCount ):
                        count += 1
                        
        return count
                        
    
    def __paint( self, grid, row, column, visited, rowCount, columnCount ):
        if ( row, column ) in visited:
            return False
        
        visited.add( ( row, column ) )
        offsets = ( ( row - 1, column ), ( row + 1, column ), ( row, column - 1 ), ( row, column + 1 ) )
        
        for offset in offsets:
            if offset not in visited:
                row, column = offset
                
                if 0 <= row < rowCount:
                    if 0 <= column < columnCount:
                        v = grid[ row ][ column ]
                        
                        if v == '1':
                            self.__paint( grid, row, column, visited, rowCount, columnCount )
        
        return True