[LeetCode]Count Sub Islands

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

왼쪽 그리드의 섬들 집합에서 오른쪽 그리드를 비교했을 때 Sub Islands는 몇개인지 구하는 문제입니다.

 

처음 시도한 답안 - 실패

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        
        m = len(grid1)
        n = len(grid1[0])

        dx = [0,1,0,-1]
        dy = [1,0,-1,0]

        grid1_path = []
        grid2_path = []

        for i in range(m):
            for j in range(n):
                if grid1[i][j] == 1:
                    queue1 = [(i,j)]
                    path1 = [(i,j)]
                    grid1[i][j] = 0

                    while queue1:
                        i, j = queue1.pop(0)

                        for idx in range(4):
                            x = i + dx[idx]
                            y = j + dy[idx]

                            if x < 0 or y < 0 or x >= m or y >= n or grid1[x][y] == 0:
                                continue

                            queue1.append((x,y))
                            path1.append((x,y))
                            grid1[x][y] = 0

                    grid1_path.append(path1)

        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    queue2 = [(i,j)]
                    path2 = [(i,j)]
                    grid2[i][j] = 0

                    while queue2:
                        i, j = queue2.pop(0)

                        for idx in range(4):
                            x = i + dx[idx]
                            y = j + dy[idx]

                            if x < 0 or y < 0 or x >= m or y >= n or grid2[x][y] == 0:
                                continue

                            queue2.append((x,y))
                            path2.append((x,y))
                            grid2[x][y] = 0

                    grid2_path.append(path2)

        count = 0
        for grid1_island in grid1_path:
            for grid2_island in grid2_path:
                if set(grid2_island) - set(grid1_island) == set():
                    count += 1

        # print(grid1_path)
        # print(grid2_path)

        return count

접근 방법

1. 처음에 시도했으나 실패했던 방법입니다.
2. grid1과 grid2를 순회하면서 방문한 포인터를 저장합니다.
3. 방문한 포인터를 set하여 차이가 나는만큼 부분 섬의 갯수라고 판단했습니다.

처음에는 두 그리드를 순회하면서 방문한 포인터를 각각 저장시킨후 set 연산을 통해 차이가 나는 지점만큼이 부분 섬의 갯수인줄 알았으나 예외케이스로 실패했습니다. grid2에만 1이 있는 경우도 부분 섬의 갯수로 잘못 카운트되어 다른 방법을 사용했습니다.

 

두번째로 시도한 답안 

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        """
        1. grid1와 grid2가 모두 1인 부분들만 남기고 나머지 grid2는 전부 0처리. (== grid2가 1이고 grid1이 0인 경우)
           이렇게하면 grid2에 sub island만 남게됨
        2. 1번에서의 sub island를 DFS를 통해 탐색하고 숫자를 구함
        """

        m = len(grid1)
        n = len(grid1[0])

        def dfs(i, j):
            dx = [0,1,0,-1]
            dy = [1,0,-1,0]

            if i < 0 or j < 0 or i >= m or j >= n or grid2[i][j] == 0:
                return

            grid2[i][j] = 0

            for idx in range(4):
                dfs(i+dx[idx], j+dy[idx])

        # grid2가 1이고 grid1이 0이면 sub island가 아니므로 0마킹을 통해 제거함
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1 and grid1[i][j] == 0:
                    dfs(i, j)

        count = 0
        # sub island만 남은 grid2에서 DFS 탐색하면서 island 수를 구함
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    dfs(i, j)
                    count += 1

        return count

접근 방법

1. 이중 순회를 통해 grid1과 grid2가 공통으로 1인 부분을 제외하고 grid2의 나머지 지점을 0 처리합니다. (DFS이용)
2. 이중 순회를 하면서 grid2가 1인 부분을 카운트하면서 탐색합니다.
3. DFS는 그리드를 벗어나지 않으면 상하좌우로 탐색하고 방문 처리만 수행합니다.

grid2가 grid1의 서브트리임을 확인하기 위한 방법은 다음과 같습니다.

grid1과 grid2가 공통으로 1인 부분을 제외하고 모두 0처리를 한다면, grid2는 grid1의 sub islands로만 구성이 됩니다.

이제는 grid2의 섬의 갯수만을 구하면 정답을 구할 수 있습니다.

 

서브 islands인 상태를 만들기 위해서 grid2를 0으로 처리하는 아이디어를 떠올리기 어려웠던 문제였습니다.