[LeetCode] 1254 | Number of Closed Islands

1254 | Number of Closed Islands
https://leetcode.com/problems/number-of-closed-islands/

 

 

 

 

작성 코드

 

접근 방법

 

1. for 문을 돌며 grid[x][y] = 0 인 곳은 dfs 으로 상하좌우 탐색 후, 한 번 돌면 count += 1
2. 모든 면이 물(1)로 둘러 쌓여야 하기 때문에, 테두리에 grid[x][y] = 0 인 곳은 dfs 상하좌우 탐색 하여 1로 변환해줌

 

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        def dfs(x, y):
            if (x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0])) or grid[x][y] == 1:
                return
            
            grid[x][y] = 1
                
            dfs(x - 1, y)
            dfs(x + 1, y)
            dfs(x, y - 1)
            dfs(x, y + 1)
            
            
        def dfs_side(x, y):
            if (x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0])) or grid[x][y] == 1:
                return
            
            grid[x][y] = 1
                
            dfs(x - 1, y)
            dfs(x + 1, y)
            dfs(x, y - 1)
            dfs(x, y + 1)
                
            
        for i in range(len(grid)):
            if grid[i][0] == 0:
                dfs_side(i, 0)
            if grid[i][-1] == 0:
                dfs_side(i, len(grid[0]) - 1)
        
        
        for j in range(len(grid[0])):
            if grid[0][j] == 0:
                dfs_side(0, j)
            if grid[-1][j] == 0:
                dfs_side(len(grid) - 1, j)
                
        answer = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    dfs(i, j)
                    answer += 1
        return answer

 

• 작성 당시, dfs 와 dfs_side 함수가 하는 일이 다르기에 따로 작성해주었으나, 내부 코드는 완전 일치함을 알 수 있음 -> 코드 간결하게