[리트코드] 695 - Max Area of Island

695. Max Area of Island

Medium

---

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

 

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

분류

배열, 깊이 우선 탐색, 너비 우선 탐색, Union-Find, 행렬

---

문제 풀이

문제 분석

이 문제는 m x n 크기의 이진 행렬 grid가 주어졌을 때, 행렬 내에서 가장 넓은 '섬'의 면적을 찾는 것을 목표로 합니다. 섬은 상하좌우(4방향)로 연결된 1들(육지)의 그룹을 의미하며, 0은 물을 나타냅니다. 그리드의 모든 가장자리는 물로 둘러싸여 있다고 가정합니다. 섬이 전혀 없을 경우 0을 반환해야 합니다.

입력:

• grid: m x n 크기의 이진 행렬. 각 요소는 0 (물) 또는 1 (육지)입니다.

출력:

• int: 가장 넓은 섬의 면적.

접근 방법

이 문제는 그리드에서 연결된 컴포넌트(Connected Component)를 찾는 전형적인 문제입니다. 이러한 유형의 문제는 너비 우선 탐색(BFS) 또는 깊이 우선 탐색(DFS) 알고리즘을 사용하여 해결할 수 있습니다.

주어진 코드는 **BFS (너비 우선 탐색)**를 사용하여 문제를 해결합니다. BFS를 선택한 이유는 다음과 같습니다:

1. 연결된 영역 탐색: BFS는 시작점에서부터 인접한 노드들을 '수평적으로' 탐색하여 현재 섬에 속하는 모든 육지 셀을 찾기에 적합합니다.
2. visited 배열 사용: 각 셀이 섬에 포함되는지 여부를 한 번만 계산하도록 visited (방문 여부) 배열을 사용합니다. 이는 중복 계산을 방지하고, 이미 탐색한 섬의 부분을 다시 탐색하여 발생하는 비효율성이나 무한 루프를 막는 데 필수적입니다.
3. 최대값 갱신: 각 섬을 찾을 때마다 그 넓이를 계산하고, 지금까지 찾은 최대 넓이와 비교하여 최종적으로 가장 넓은 섬의 면적을 반환합니다.

구현 설명

주어진 코드는 BFS 알고리즘을 사용하여 그리드를 탐색하며 각 섬의 면적을 계산하고, 그 중 최대값을 찾아 반환합니다.

1단계: 초기 설정 및 그리드 순회

• answer = 0: 발견된 가장 큰 섬의 면적을 저장할 변수를 0으로 초기화합니다.
• n = len(grid), m = len(grid[0]): 그리드의 행(n)과 열(m)의 크기를 가져옵니다.
• visited = [[False] * m for _ in range(n)]: 모든 셀의 방문 여부를 추적할 2차원 배열을 생성합니다. 초기에는 모든 셀이 방문되지 않았으므로 False로 설정됩니다.
• directions = [(1,0),(-1,0),(0,1),(0,-1)]: 상하좌우 4방향으로 이동하기 위한 델타 값(dx, dy)을 정의합니다.
• 두 개의 중첩 for 루프 (for i in range(n), for j in range(m))를 사용하여 그리드의 모든 셀 (i, j)을 순회합니다.
• if grid[i][j] and not visited[i][j]:: 현재 셀 (i, j)이 육지(1)이고 아직 방문하지 않은 셀인 경우에만 새로운 섬의 시작점으로 간주하고 BFS 탐색을 시작합니다.

2단계: BFS를 통한 섬 탐색 및 넓이 계산

• queue = deque(): 현재 섬을 탐색하기 위한 큐를 생성합니다. deque는 양쪽 끝에서 빠른 삽입/삭제를 지원하여 BFS에 효율적입니다.
• queue.append((i,j)): 현재 시작 셀 (i, j)를 큐에 추가합니다.
• cnt = 0: 현재 탐색 중인 섬의 면적을 계산할 변수를 0으로 초기화합니다.
• visited[i][j] = True: 시작 셀을 방문했음을 표시합니다.
• while queue: 루프를 시작하여 큐가 빌 때까지 반복합니다. 큐가 비면 현재 섬의 모든 육지 셀을 탐색한 것입니다.
• x,y = queue.popleft(): 큐에서 가장 먼저 들어간 셀 (x, y)를 가져옵니다.
• cnt += 1: (x, y)는 현재 섬의 일부이므로, 현재 섬의 면적 cnt를 1 증가시킵니다.

3단계: 인접 셀 탐색 및 큐 추가

• for dx,dy in directions:: 현재 셀 (x, y)의 상하좌우 4방향 이웃 셀을 탐색합니다.
• sx,sy = x+dx, y+dy: 새로운 이웃 셀의 좌표 (sx, sy)를 계산합니다.
• if 0<=sx<n and 0<=sy<m and grid[sx][sy] and not visited[sx][sy]:: 다음 세 가지 조건을 모두 만족하는 경우에만 이웃 셀을 큐에 추가합니다.
  • 0<=sx<n and 0<=sy<m: 이웃 셀이 그리드 경계 내에 있는지 확인합니다.
  • grid[sx][sy]: 이웃 셀이 육지(1)인지 확인합니다.
  • not visited[sx][sy]: 이웃 셀이 아직 방문하지 않은 셀인지 확인합니다.
• 위 조건을 만족하면, queue.append((sx,sy))를 통해 이웃 셀을 큐에 추가하고, visited[sx][sy] = True로 설정하여 다시 방문하지 않도록 표시합니다.

4단계: 최대 넓이 업데이트 및 결과 반환

• while queue: 루프가 종료되면, 현재 시작점에서부터 연결된 하나의 섬에 대한 탐색이 모두 끝난 것입니다. cnt 변수에는 이 섬의 총 면적이 저장됩니다.
• answer = max(answer,cnt): 지금까지 발견된 최대 섬의 면적 answer와 현재 섬의 면적 cnt를 비교하여 더 큰 값으로 answer를 업데이트합니다.
• 모든 그리드 셀에 대한 순회가 끝나면, answer에는 그리드 내의 모든 섬 중에서 가장 넓은 섬의 면적이 저장되어 있습니다. 이 값을 return answer로 반환합니다.
• print(grid, visited) 줄은 디버깅 용도로 보이며, 문제 해결 로직의 필수적인 부분은 아닙니다.

⏱복잡도 분석

시간 복잡도: O(N * M)

• 그리드의 모든 셀 (N * M)을 중첩된 for 루프를 통해 한 번씩 확인합니다.
• 각 셀에 대해 BFS 탐색이 시작되면, visited 배열 덕분에 각 셀은 큐에 최대 한 번만 추가되고 한 번만 추출됩니다.
• 큐에서 셀 하나를 추출할 때마다 해당 셀의 4방향 이웃을 확인하는 작업은 상수 시간(O(1))이 걸립니다.
• 따라서, 모든 셀을 한 번씩 방문하고 처리하는 데 필요한 총 시간은 그리드의 셀 개수 N * M에 비례합니다.

공간 복잡도: O(N * M)

• visited 2차원 배열: 그리드와 같은 크기인 N * M의 공간을 사용합니다.
• queue: 최악의 경우 (그리드 전체가 하나의 거대한 섬일 때), 큐에 N * M개의 셀이 저장될 수 있습니다.
• 따라서, 총 공간 복잡도는 그리드 크기 N * M에 비례합니다.

핵심 포인트

1. BFS (너비 우선 탐색) 또는 DFS (깊이 우선 탐색) 활용: 그리드에서 연결된 요소를 찾고 그 크기를 계산하는 가장 효율적인 방법입니다. 코드에서는 BFS를 사용하여 시작점에서 가까운 노드부터 탐색합니다.
2. visited 배열 사용: 이미 방문한 셀을 다시 탐색하지 않도록 visited 배열을 사용하여 중복 계산을 방지하고, 알고리즘의 시간 복잡도를 최적화합니다. 이는 무한 루프를 방지하는 데도 필수적입니다.
3. 경계 조건 및 육지 확인: BFS 탐색 중 인접한 셀을 큐에 추가하기 전에, 해당 셀이 그리드 경계 내에 있는지(0<=sx<n and 0<=sy<m), 그리고 육지(grid[sx][sy] == 1)인지 반드시 확인해야 합니다.

풀이 코드

from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        answer = 0
        n = len(grid)
        m = len(grid[0])

        visited = [[False] * m for i in range(n)]
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        for i in range(n):
            for j in range(m):
                if grid[i][j] and not visited[i][j]:
                    queue = deque()
                    queue.append((i,j))
                    cnt = 0
                    visited[i][j] = True

                    while queue:
                        x,y = queue.popleft()
                        cnt += 1
                        for dx,dy in directions:
                            sx,sy = x+dx, y+dy
                            if 0<=sx<n and 0<=sy<m and grid[sx][sy] and not visited[sx][sy]:
                                queue.append((sx,sy))
                                visited[sx][sy] = True

                    answer = max(answer,cnt)

        print(grid, visited)
        return answer