LeetCode 풀기 - 695. Max Area of Island

695. Max Area of Island

https://leetcode.com/problems/max-area-of-island/

Max Area of Island - LeetCode

문제)

솔루션1)

m x n의 island를 dfs 탐색해 나갑니다.

visited 별도의 space를 만들어서 방문했던 곳은 skip 처리합니다.

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_row = len(grid)
        max_col = len(grid[0])

        max_island_area = 0

        visited = []
        for col in range(max_row):
            visited.append([0] * max_col)

        def dfs(row, col, island_areas):
            # check boundary
            if not (0 <= row < max_row and 0 <= col < max_col):
                return

            # 이미 방문 했다면
            if visited[row][col]:
                return

            # 방문 체크
            visited[row][col] = 1

            # 현재 위치가 바다이면 리턴
            if grid[row][col] == 0:
                return

            # 현재 위치가 island 이므로
            island_areas.append([row, col])

            # 상, 하, 좌, 우 탐색
            [dfs(row + x, col + y, island_areas) for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]]

        for row in range(max_row):
            for col in range(max_col):
                island_areas = []
                dfs(row, col, island_areas)
                max_island_area = max(len(island_areas), max_island_area)

        return max_island_area

솔루션2)

visited라는 별도의 메모리 공간을 제거하는 방법이 있습니다.

방문지가 island 였다면 바다(0)로 변경해버리면 됩니다.

 

아래 코드는 visited 배열을 삭제한 코드입니다.

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_row = len(grid)
        max_col = len(grid[0])
        max_island_area = 0

        def dfs(row, col, island_areas):
            # check boundary
            if not (0 <= row < max_row and 0 <= col < max_col):
                return
            
            # 현재 위치가 바다이면 리턴
            if grid[row][col] == 0:
                return
            
            # island를 바다로 변경 처리 함. 다음에 다시 방문하지 않도록
            grid[row][col] = 0

            # 현재 위치가 island 이므로
            island_areas.append([row, col])

            # 상, 하, 좌, 우 탐색
            [dfs(row + x, col + y, island_areas) for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]]

        for row in range(max_row):
            for col in range(max_col):
                island_areas = []
                dfs(row, col, island_areas)
                max_island_area = max(len(island_areas), max_island_area)

        return max_island_area

솔루션3)

기존 코드는 island의 크기를 island_area에 [row, col]을 계속 추가한 다음에 카운트를 세서(리스트의 크기) island의 사이즈를 측정하였습니다. 메모리 낭비나 오버헤드가 있기 때문에 이를 제거할 필요가 있습니다.

 

dfs() 함수 내에서 island 방문 했던 곳에 count를 리턴하도록 처리하였습니다.

class Solution:
    def maxAreaOfIsland(self, grid):
        max_row = len(grid)
        max_col = len(grid[0])
        max_island_area = 0

        def dfs(row, col):
            # check boundary
            if not (0 <= row < max_row and 0 <= col < max_col):
                return 0

            # 현재 위치가 바다이면 리턴
            if grid[row][col] == 0:
                return 0

            # island를 바다로 변경 처리 함. 다음에 다시 방문하지 않도록
            grid[row][col] = 0

            # 상, 하, 좌, 우 탐색
            up = dfs(row - 1, col)
            down = dfs(row + 1, col)
            left = dfs(row, col - 1)
            right = dfs(row, col + 1)

            return up + down + left + right + 1

        for row in range(max_row):
            for col in range(max_col):
                island_area = dfs(row, col)
                max_island_area = max(island_area, max_island_area)

        return max_island_area