Graphs: 695. Max Area of Island ★

695. Max Area of Island

 

BFS로 풀기

from typing import List
from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # 섬 개수 및 최대 면적을 계산하는 함수
        # Count the number of islands and calculate the maximum area
        
        # 네 방향 이동: 상, 하, 좌, 우
        # Directions for movement: up, down, left, right
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        
        # 그리드의 행(Row)과 열(Column) 크기
        # Number of rows and columns in the grid
        ROWS, COLS = len(grid), len(grid[0])

        # 섬의 개수 및 최대 면적을 저장할 변수
        # Variables to store the number of islands and the maximum area
        isIlands = 0  # 섬의 개수 / Number of islands
        maxArea = 0   # 섬의 최대 면적 / Maximum area of an island

        # 방문한 위치를 저장할 집합
        # Set to store visited positions
        visit = set()

        # BFS를 이용하여 섬의 면적을 계산하는 함수
        # Function to calculate the area of an island using BFS
        def bfs(r, c):
            # 큐를 생성하고 시작 위치를 추가
            # Initialize a queue and add the starting position
            q = deque()
            q.append((r, c))
            
            # 현재 위치를 방문 처리
            # Mark the current position as visited
            visit.add((r, c))
            
            # 섬의 초기 면적은 1
            # Initial area of the island is 1
            area = 1

            # BFS를 통해 연결된 섬의 영역 탐색
            # Explore connected areas of the island using BFS
            while q:
                r, c = q.popleft()
                for dr, dc in directions:
                    # 새 위치 계산
                    # Calculate new position
                    R, C = r + dr, c + dc

                    # 유효한 범위 내에서, 방문하지 않았고, 섬인 경우
                    # Check if it's within bounds, not visited, and part of the island
                    if R in range(ROWS) and C in range(COLS) and grid[R][C] == 1 and (R, C) not in visit:
                        # 큐에 추가하고 방문 처리
                        # Add to the queue and mark as visited
                        q.append((R, C))
                        visit.add((R, C))
                        
                        # 면적 증가
                        # Increment the area
                        area += 1
            
            # 탐색한 섬의 전체 면적 반환
            # Return the total area of the explored island
            return area

        # 모든 셀을 순회하며 섬을 찾음
        # Iterate through all cells to find islands
        for r in range(ROWS):
            for c in range(COLS):
                # 섬이고 방문하지 않은 경우
                # If it's part of an island and not visited
                if grid[r][c] == 1 and (r, c) not in visit:
                    # BFS를 실행하여 최대 면적 갱신
                    # Execute BFS and update the maximum area
                    maxArea = max(maxArea, bfs(r, c))
                    
                    # 섬 개수 증가
                    # Increment the island count
                    isIlands += 1

        # 섬의 최대 면적 반환
        # Return the maximum area of the islands
        return maxArea

 

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # 섬 개수 => bfs, 큐
        # 섬의 최대 면적 => dfs, 재귀
        # 방향: 4방향
        # 1: 섬, 0: 물
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        ROWS, COLS = len(grid), len(grid[0])

        isIlands = 0 # 섬개수
        maxArea = 0 # 넓이
        visit = set()

        def bfs(r, c):
            q = deque()
            q.append((r, c))
            visit.add((r, c))
            area = 1

            while q:
                r, c = q.popleft()
                for dr, dc in directions:
                    R, C = r+dr, c+dc

                    if R in range(ROWS) and C in range(COLS) and grid[R][C] == 1 and (R, C) not in visit:
                        q.append((R, C))
                        visit.add((R, C))
                        area += 1
            return area


        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1 and (r, c) not in visit:
                    maxArea = max(maxArea, bfs(r, c))
                    isIlands += 1

        return maxArea

DFS 로 풀기

from typing import List

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # grid의 행과 열 크기를 구합니다.
        # Determine the number of rows and columns in the grid.
        ROWS, COLS = len(grid), len(grid[0])

        # 방문한 셀을 저장하기 위한 집합입니다.
        # A set to store visited cells.
        visit = set()

        def dfs(r, c):
            # 종료 조건: grid 경계를 벗어나거나, 물(0)이거나, 이미 방문한 경우.
            # Base case: Out of bounds, water (0), or already visited.
            if (min(r, c) < 0 or r == ROWS or c == COLS or grid[r][c] == 0 or (r, c) in visit):
                return 0

            # 현재 위치를 방문했다고 표시합니다.
            # Mark the current position as visited.
            visit.add((r, c))

            # 현재 셀(1)을 포함하여 네 방향으로 재귀 호출합니다.
            # Include the current cell (1) and recursively call in four directions.
            return (1 + dfs(r + 1, c) + dfs(r, c + 1) + dfs(r - 1, c) + dfs(r, c - 1))

        # 최대 영역을 저장할 변수입니다.
        # Variable to store the maximum area.
        area = 0

        # 모든 셀을 순회하며 DFS를 실행합니다.
        # Traverse all cells and execute DFS.
        for r in range(ROWS):
            for c in range(COLS):
                # 최대 영역을 갱신합니다.
                # Update the maximum area.
                area = max(area, dfs(r, c))

        # 최대 영역을 반환합니다.
        # Return the maximum area.
        return area

 

최종 코드: DFS + visit (set) 사

좋아요! 이 문제는 이전 "섬의 개수" 문제와 거의 비슷한 구조인데,
이번엔 섬의 개수 세는 게 아니라, 각 섬의 면적을 구해서 그 중 최대값을 리턴하는 거예요.

---

✅ 핵심 아이디어:

• 1을 만나면 DFS를 돌려서 섬의 전체 면적(1의 개수) 을 계산
• DFS가 끝날 때마다 최댓값 갱신
• visit은 set()을 사용해서 중복 방문 방지

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # 섬 개수: dfs, visit(set)
        # 섬 면적: dfs
        ROWS, COLS = len(grid), len(grid[0])
        directions = [[1,0], [-1,0], [0,1], [0,-1]]
        visit = set()

        def dfs(r, c):
            if r<0 or c<0 or r>=ROWS or c>=COLS or grid[r][c] == 0 or (r,c) in visit:
                return 0

            # 현재 방문 처리
            visit.add((r,c))
            area = 1 # 현재도 넓이도 추가

            for dr, dc in directions:
                area += dfs(dr+r, dc+c)
            return area

        max_area = 0

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1 and (r, c) not in visit:
                    max_area = max(max_area, dfs(r, c))
        return max_area