리트코드_섬의 개수

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

• 주어진 grid가 그래프는 아니지만, 사실상 동서남북이 연결된 그래프로 가정
• grid 중 '1'인 부분을 찾아 해당 지점부터 동서남북으로 DFS순회
• 순회할때 방문한 grid[i][j]의 값을 '0'으로('1'이 아닌 다른 값으로) 바꿔서 다시 방문하지 않도록 한다.
• DFS의 재귀를 벗어날때마다 섬의 개수를 하나 씩 증가시킨다.

💡 전체 소스 코드

class Solution:
    def dfs_recursion(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_recursion(grid, i - 1, j)
            self.dfs_recursion(grid, i + 1, j)
            self.dfs_recursion(grid, i, j - 1)
            self.dfs_recursion(grid, i, j + 1)
            
    def numIslands(self, grid: List[List[str]]) -> int:
        
        cnt = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs_recursion(grid, i, j)
                    cnt += 1
                    
        return cnt