[파이썬 알고리즘 인터뷰] 32. 섬의 개수

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

32. 섬의 개수

leetcode 200. Number of Islands 문제입니다.

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

 

 

풀이

 1은 섬을 의미합니다. grid에서 섬인 인덱스를 찾으면, dfs로 확장해 나갑니다.

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

    def dfs(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

        # 동서남북 탐색
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                # 모든 육지 탐색 후 카운트 1 증가
                count += 1
    return count