오늘의 문제는 Leetcode에서 Number Of Islands 이라는 꽤 흔한 인터뷰 질문입니다.

질문

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

접근

솔직히 말해서 이 문제에 대해 깊이 우선 탐색을 사용할 생각을 하지 않았습니다. 처음에는 그리드의 각 요소를 반복하고 다른 데이터 구조의 모든 인접 요소를 추적하는 무차별 대입 접근 방식을 생각했습니다. 나는 그래프와 트리의 맥락에서 DFS와 BFS에 대해 배웠으므로 DFS 또는 BFS 알고리즘이 여기에 적절할 것이라고 즉시 클릭하지 않았습니다.

DFS 알고리즘을 사용하기 시작하면 이 특정 문제에 적용할 수 있는 방법을 찾아야 했습니다. 그리드의 왼쪽 위 모서리(좌표 0, 0)에서 시작하고 1과 같은 그리드 공간을 만나면 무언가를 하고 싶다는 것을 알고 있었습니다. 1과 같은 그리드 공간을 만나면 우리가 섬에 부딪혔다는 것을 알고, 이 섬이 얼마나 큰지 알아보기 위해 주변 그리드 요소를 탐색해야 합니다.

대략적이고 전반적인 공격 계획은 그리드를 반복하고 '1'을 찾을 때마다 '1'을 '0'으로 바꾼 다음 전체 그리드가 소진될 때까지 인접한 모든 공간에서 DFS를 실행하는 것입니다. 1과 같은 시작 공간을 사용하여 DFS를 재귀적으로 실행하면 섬의 '총 크기'를 얻을 수 있으며, 그런 다음 실제로 총 섬 수의 실행 횟수를 유지하는 데 사용할 수 있습니다.

해결책

거의 항상 알고리즘의 핵심을 살펴보기 전에 가장 먼저 할 일은 가능한 극단적인 경우를 생각하는 것입니다. 나는 일반적으로 이 단계에서 그것들을 모두 잡지는 않지만, 내가 먼저 쓸 일반적인 경우는 입력이 0, 비어 있음, null, 없음 등인 경우입니다.

def num_islands(grid: List[List[str]]) -> int:
    # variable to hold the number of islands
    island_count = 0

    # first check if there are values in the grid
    if not grid:
        return island_count

다음으로, 내 솔루션이 범위를 벗어나지 않도록 그리드 길이와 너비를 설정하고 싶습니다. 각각 m 및 n 를 설정하여 이 작업을 수행합니다.

    # m will represent the number of rows in our grid
    m = len(grid)

    # n will represent the number of columns in our grid
    n = len(grid[0])

이제 내 경계를 모두 정리했으므로 깊이 우선 검색 알고리즘을 작성하는 솔루션의 핵심으로 이동할 시간입니다. GeeksforGeeks , basecs 등의 DFS에 대한 설명과 코드 샘플이 포함된 훌륭한 리소스가 온라인에 많이 있으므로 여기에서 자세한 내용은 다루지 않겠습니다.

    def dfs(i, j):
        # check if i and j are still on the grid
        # check if the current spot doesn't already equal 1
        if(i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != "1"):
            return

        # otherwise
        else:
            # set current grid space to 0
            grid[i][j] = 0
            # run dfs on all surrounding elements
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

DFS를 구현하기 위해 도우미 함수를 사용하고 있으며 이 함수는 현재 그리드 좌표를 나타내는 매개변수i 및 j를 허용합니다. (3, 2)에서 첫 번째 '1'을 만난 다음 dfs(3, 2)를 호출한다고 가정해 보겠습니다.

즉시 우리는 위치가 유효한지 확인하고 현재 자리가 이미 1과 같지 않은지 확인합니다. 이러한 경우 중 하나라도 사실이면 일찍 돌아올 수 있습니다. 그런 다음 그리드 공간이 0(물 공간임을 의미)인지 확인해야 합니다. 함수를 종료할 수도 있습니다.

그렇지 않으면 현재 그리드 공간은 '1'과 같아야 하므로 이를 '0'으로 뒤집고 모든 인접 요소(위, 아래, 왼쪽, 오른쪽)에서 dfs 도우미 함수를 재귀적으로 호출합니다.

솔직히 이 시점에서 대부분의 힘든 작업은 끝났습니다! 🎉 그리드를 반복하고 1을 식별하는 코드를 작성하기만 하면 됩니다!

    # initial for loop to iterate through the grid
        for i in range(m):
            # iterating through each row
            for j in range(n):
                # if current grid space is 1
                if(grid[i][j] == "1"):
                    # increment island count
                    island_count += 1
                    # run dfs using the current spot as the root
                    dfs(i, j)
                # if grid space is 0
                else:
                    # continue searching
                    continue

        # return count when done          
        return island_count

여기 있습니다, 최종 형태입니다!

    def num_islands(grid: List[List[str]]) -> int:
        # variable to hold the number of islands
        island_count = 0

        # first check if there are values in the grid
        if not grid:
            return island_count

        # set the lengths:
        # m represents the number of rows
        m = len(grid)
        # n represents the number of columns
        n = len(grid[0])

        # definition of depth-first search
        def dfs(i, j):
            # check if i and j are still on the grid
            # check if the current grid spot doesn't already equal 1
            if(i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != "1"):
                return

            # otherwise
            else:
                # set current grid space to 0
                grid[i][j] = 0
                # run dfs on all surrounding elements
                dfs(i - 1, j)
                dfs(i + 1, j)
                dfs(i, j - 1)
                dfs(i, j + 1)

        # initial for loop to iterate through the grid
        for i in range(m):
            # iterating through each row
            for j in range(n):
                # if current grid space is 1
                if(grid[i][j] == "1"):
                    # increment island count
                    island_count += 1
                    # run dfs using the current spot as the root
                    dfs(i, j)
                # if grid space is 0
                else:
                    # continue searching
                    continue

        # return count when done          
        return island_count

복잡성

이 구현의 시간 복잡도는 O(mn)입니다. 여기서 m는 그리드의 행 수이고 n는 열 수입니다.