[leetcode] 1905. Count Sub Islands 풀이 #2

안녕하세요. 이번에는 어제 풀었던 [ leetcode] 1905. Count Sub Islands 문제를 다시 풀어봤습니다.

 

다시 풀었던 이유는... Runtime, Memory 효율성이 매우 낮았기 때문입니다.

처참한 Runtime, Memory 효율성

• 참고: https://goodahn.tistory.com/241

뭐가 문제였는지 이전 문제 풀이부터 검토해보겠습니다!

1. 이전 문제 풀이

저는 이전에 connected component에 꽂혀서 다음과 같이 문제를 해결했습니다.

 

1. grid1과 grid2에 있는 connected componet들을 전부 찾습니다.

• Depth First Search를 이용해서 connected component를 찾을 수 있습니다.

2. grid2에 있는 connected component 내의 모든 좌표가 grid1의 동일한 connected component에 있는지 하나씩 확인합니다.

• grid2의 좌표에 대해서 grid1의 어떤 connected component에 있는지 쉽게 확인할 수 있도록 1에서 데이터를 준비해둡니다.

3. 2에서 확인한 sub-island의 수를 반환합니다.

 

 

바로 빨간색으로 표시한 부분에서 비효율이 발생하고 있었습니다.

 

grid1의 connectecd component를 찾았던 이유는

grid2의 connected component가 grid1의 동일한 connected component에 포함되는지 확인하기 위함이었습니다.

 

그런데 grid2의 connected component가 grid1에 포함되어 있다는 것은 이미 grid1의 동일한 connected component에 포함되어 있다는 뜻입니다.

 

2. 개선된 풀이

위의 분석을 바탕으로 찾은 Runtime, Memory 효율성을 높일 수 있는 요소입니다.

• grid1의 connected component를 찾지 않는다.
• grid2의 connected component를 찾을 때, grid1에 포함되어 있는지만 검사한다.

짜잔! 이렇게 개선하니 Runtime과 메모리 효율성이 대폭 상승했습니다!

개선된 Runtime, Memory 효율성

+ 코드

이번에도 부족한 코드 공유드립니다!

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        result = 0
        
        for row_idx in range(len(grid2)):
            for col_idx in range(len(grid2[0])):
                if grid2[row_idx][col_idx] == 1:
                    if dfs_with_checking_subisland(grid1, grid2, row_idx, col_idx):
                        result += 1
        return result

def dfs_with_checking_subisland(grid1: List[List[int]], grid2: List[List[int]], row_idx: int, col_idx: int):
    grid2[row_idx][col_idx] = 0
    visited_count = 0
    contained_count = 0

    queue = [(row_idx, col_idx)]
    while len(queue) > 0:
        (row_idx, col_idx) = queue.pop()
        visited_count += 1
        if grid1[row_idx][col_idx] == 1:
            contained_count += 1
        if row_idx > 0 and grid2[row_idx-1][col_idx] == 1:
            grid2[row_idx-1][col_idx] = 0
            queue.append((row_idx-1, col_idx))
        if row_idx < len(grid2) - 1 and grid2[row_idx+1][col_idx] == 1:
            grid2[row_idx+1][col_idx] = 0
            queue.append((row_idx+1, col_idx))
        if col_idx > 0 and grid2[row_idx][col_idx-1] == 1:
            grid2[row_idx][col_idx-1] = 0
            queue.append((row_idx, col_idx-1))
        if col_idx < len(grid2[0])-1 and grid2[row_idx][col_idx+1] == 1:
            grid2[row_idx][col_idx+1] = 0
            queue.append((row_idx, col_idx+1))

    return contained_count == visited_count