1254. Number of Closed Islands

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

Number of Closed Islands - LeetCode

 

닫힌 섬의 개수를 찾는 문제

dfs로 해결이 가능하다.

 

물에 둘러쌓인 고립된 섬의 갯수만 찾는 것인데,

조건에서 모서리에 있는 육지는 섬이 아니라 한다.

모서리 부분에 연결된 육지를 물로 치환해주고

 

그 다음의 섬의 갯수를 찾으면 된다.

 

 

class Solution(object):
    def closedIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
            
        def exclude():
            
            for i in range(0, len(grid), 1):
                for j in range(0, len(grid[0]),1):
                    
                    if (i==0 or j==0 or i==len(grid)-1 or j == len(grid[0])-1) and grid[i][j] == 0:
                        dfs(i,j,1)
                        
    
        def dfs(r, c, val):
            
            if grid[r][c] == 0:
                grid[r][c] = val
           
                if r+1 < len(grid) :
                    dfs(r+1,c,val)
                if c-1 >= 0:
                    dfs(r, c-1, val)
                if r-1 >= 0:
                    dfs(r-1, c, val)
                if c+1 < len(grid[0]):
                    dfs(r, c+1, val)
    

        
            
        def printgrid(grid):
            
            for i in grid:
                print(i)
        exclude()
        
        
        #printgrid(grid)
        
        closed_island = 0
        for i in range(0, len(grid), 1):

            for j in range(0, len(grid[0]), 1):
                
                if grid[i][j] == 0:
                    pass
                    dfs(i,j, grid)
                    closed_island+=1
                    #printgrid(grid)
                    #print("------------------")
        
        return closed_island