📕문제

[[Leetcode] 200. Number of Islands]

문제 설명

육지(1)와 바다(0)로 이루어진 m * n 테이블에서 존재하는 섬의 개수를 구하는 문제다.

---

📝풀이

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:        
        
        def findNext(x, y):
            grid[y][x] = '0'
            if y-1 >= 0 and grid[y-1][x] == '1':
                findNext(x, y-1)
            if len(grid) > y+1 and grid[y+1][x] == '1':
                findNext(x, y+1)
            if x-1 >= 0 and grid[y][x-1] == '1':
                findNext(x-1, y)
            if len(grid[0]) > x+1 and grid[y][x+1] == '1':
                findNext(x+1, y)


        count = 0
        for y in range(len(grid)):
            for x in range(len(grid[0])):
                if grid[y][x] == '1':
                    findNext(x, y)
                    count += 1
        
        return count

• 테이블을 순회하다 '1'을 발견하면 탐색을 시작한다.
• 중복 탐색을 방지하기 위해 해당 칸을 '0'으로 설정한다.
• 상하좌우로 탐색해 범위를 벗어나지 않고 '1'인경우 함수를 재귀호출한다.
• 탐색이 끝나면 count를 1 증가시킨다.