파이썬 알고리즘 인터뷰 32번 문제 : 섬의 개수

-문제 : 1을 육지로 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라. (연결되어 있는 1의 덩어리 개수를 구하라)

 

-풀이 : 깊이우선탐색(DFS)을 사용하였다.

 

->입력1

11110

11010

11000

00000

 

->출력1

1

 

 

->입력2

11000

11000

00100

00011

 

->출력2

3

 

 

class Solution(object):
    def dfs(self ,grid, i, j):
        # 더 이상 땅이 아닌 경우, 종료
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
            return

        grid[i][j] = '0'

        self.dfs(grid, i+1, j)
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i + 1, j)

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        # 예외처리
        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)
                    # 모든 육지 탐색 후 카운트 1 증가
                    count += 1
        return count



    """
    Runtime: 168 ms, faster than 19.83% of Python online submissions for Number of Islands.
    Memory Usage: 21.4 MB, less than 58.62% of Python online submissions for Number of Islands.
    """

 

 

출처  : 파이썬 알고리즘 인터뷰 (95가지 알고리즘 문제풀이로 완성하는 코딩테스트, 박상길 지음)