[LeetCode] 1905 | Count Sub Islands

1905 | Count Sub Islands
https://leetcode.com/problems/count-sub-islands/

 

 

 

작성 코드

 

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        def dfs(x, y):
            if x < 0 or x >= len(grid2) or y < 0 or y >= len(grid2[0]) or grid2[x][y] == 0:
                return []
            
            grid2[x][y] = 0
            
            return [[x, y]] + dfs(x - 1, y) + dfs(x + 1, y) + dfs(x, y - 1) + dfs(x, y + 1)
            
        answer = 0
        islands = []
        
        for i in range(len(grid2)):
            for j in range(len(grid2[0])):
                if grid2[i][j] == 1:
                    islands.append(dfs(i , j))
                    
        for island in islands:
            for n, m in island:
                if grid1[n][m] == 0:
                    answer -= 1
                    break
            answer += 1
            
        return answer

 

• grid2 for문을 돌면서 grid2[i][j]가 1이라면 dfs 를 돌아줌으로써 섬의 좌표를 islands에 저장함
• islands를 돌면서 grid[n][m]이 0이라면 answer에 -1을 해줌 / 마지막에 answer +1
• 즉, grid2에서는 1인 좌표가 grid1에서 0이라면 count 안 해주는 것

 

• 시간 초과 발생

 

이상 코드

 

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        def dfs(x, y):
            if x < 0 or x >= len(grid2) or y < 0 or y >= len(grid2[0]) or grid2[x][y] == 0:
                return
            
            grid2[x][y] = 0
            

            dfs(x - 1, y)
            dfs(x + 1, y)
            dfs(x, y - 1)
            dfs(x, y + 1)
            
        for i in range(len(grid2)):
            for j in range(len(grid2[0])):
                if grid2[i][j] == 1 and grid1[i][j] == 0:
                    dfs(i, j)
                    
        answer = 0
        for i in range(len(grid2)):
            for j in range(len(grid2[0])):
                if grid2[i][j] == 1:
                    dfs(i, j)
                    answer += 1
                    
        return answer
        
# [참고] https://leetcode.com/problems/count-sub-islands/discuss/1284306/98-faster-oror-Simple-approach-oror-well-explained

 

• grid2에서는 1이면서 grid0에서는 0인 [x][y] 좌표를 grid2에서 dfs로 탐색하며 0으로 처리해줌
• 처리한 후 grid2의 섬의 개수를 세주면 됨