17. 그래프 순회 - 섬의 개수

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

Number of Islands - LeetCode

 

 입력값이 정확히 그래프는 아니지만 사실상 동서남북이 모두 연결된 그래프로 가정하고 동일한 형태로 처리할 수 있으며, 네 방향 각각 DFS 재귀를 이용해 탐색을 끝마치면 1이 증가하는 형태로 육지의 개수를 파악할 수 있다.

class Solution:
    def numIslands(self, grid):
        
        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)
                    count+=1

        return count