[leetcode] 1905. Count Sub Islands 풀이

안녕하세요. 오늘은 leetcode에서 1905. Count Sub Islands 문제를 풀어봤습니다.

• https://leetcode.com/problems/count-sub-islands/description/

1. 문제

이 문제에서는 크기가 같은 grid1, grid2, 2개의 grid가 주어지고, grid2에 있는 island 중 grid1에 있는 island의 sub-island인 island가 몇 개 있는지 찾아야 합니다.

• grid에서 0인 부분은 바다이고 1인 부분은 섬 부분입니다.

 

grid는 격자 지도인 것을 아실테지만 island가 무엇인지 생소하시겠죠?

문제에서 말하는 island는 다름이 아니라 grid에 있는 connected component를 뜻합니다.

 

connected component는 단어 그대로 연결되어 있는 vertex들을 의미합니다.

다음 grid에는 connected component가 [1, 4], [3], [8, 9]로 3개 있습니다.

connected component 예시

 

그러면 grid2에 있는 island가 grid1의 island의 sub-island라는 것은 무슨 뜻일까요?

grid2에 있는 island의 모든 좌표가 grid1의 동일한 island에 포함되어 있을 때 sub-island라고 표현합니다.

 

다음 예시에서는 grid2의 2번과 4번 island만 grid1의 sub-island라고 할 수 있습니다.

sub-island 예시

 

 

2. 문제 풀이

저는 다음과 같이 접근하여 문제를 해결했습니다.

 

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의 수를 반환합니다.

+ 코드

부족하지만 저의 풀이도 공유드립니다 ㅎ...

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        result = 0
        
        cc_list_of_grid1, cc_dict_of_grid1 = find_cc_list(grid1)
        cc_list_of_grid2, cc_dict_of_grid2 = find_cc_list(grid2)

        for cc in cc_list_of_grid2:
            grid1_color = -1
            for pos, color in cc.items():
                if pos not in cc_dict_of_grid1:
                    break
                tmp_grid1_color = cc_dict_of_grid1[pos]
                if grid1_color == -1:
                    grid1_color = tmp_grid1_color
                elif grid1_color != tmp_grid1_color:
                    break
            else:
                result += 1
        return result
    
def find_cc_list(grid: List[List[int]])-> Tuple[List[Dict], Dict[int, Dict[Tuple[int, int], int]]]:
    cc_list = []
    cc_dict = {}
    color = 2
    for row_idx in range(len(grid)):
        for col_idx in range(len(grid[0])):
            if grid[row_idx][col_idx] == 1:
                cc = dfs(grid, row_idx, col_idx, color)
                cc_list.append(cc)
                cc_dict.update(cc)
                color += 1
    return (cc_list, cc_dict)

def dfs(grid: List[List[int]], row_idx: int, col_idx: int, color: int):
    queue = [(row_idx, col_idx)]
    visited = {}
    while len(queue) > 0:
        (row_idx, col_idx) = queue.pop()
        if row_idx > 0 and grid[row_idx-1][col_idx] == 1 and (row_idx-1, col_idx) not in visited:
            visited[(row_idx-1, col_idx)] = -1
            queue.append((row_idx-1, col_idx))
        if row_idx < len(grid) - 1 and grid[row_idx+1][col_idx] == 1 and (row_idx+1, col_idx) not in visited:
            visited[(row_idx+1, col_idx)] = -1
            queue.append((row_idx+1, col_idx))
        if col_idx > 0 and grid[row_idx][col_idx-1] == 1 and (row_idx, col_idx-1) not in visited:
            visited[(row_idx, col_idx-1)] = -1
            queue.append((row_idx, col_idx-1))
        if col_idx < len(grid[0])-1 and grid[row_idx][col_idx+1] == 1 and (row_idx, col_idx+1) not in visited:
            visited[(row_idx, col_idx+1)] = -1
            queue.append((row_idx, col_idx+1))

        visited[(row_idx, col_idx)] = color
        grid[row_idx][col_idx] = color

    return visited