← 전체 회차
a-082-max-area-of-island2026-08-09mediumleetcode #695neetcode150

섬의 최대 넓이

#array#depth-first-search#breadth-first-search#union-find#matrix
↗ leetcode #695 · a-082-max-area-of-island
01

문제

· problem
P.a-082-max-area-of-island

섬의 최대 넓이

↗ leetcode #695

m x n 크기의 이진 행렬 grid가 주어집니다. 섬은 1(육지)들로 이루어진 그룹으로, 4방향(상하좌우)으로 연결되어 있습니다. 모든 모서리는 물로 둘러싸여 있다고 가정할 수 있습니다. 섬의 넓이는 섬에 속한 값 1인 셀의 개수입니다. grid에서 섬의 최대 넓이를 반환합니다. 섬이 없으면 0을 반환합니다.

제약
  • · m == grid.length
  • · n == grid[i].length
  • · 1 ≤ m, n ≤ 50
  • · grid[i][j] is either 0 or 1
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[[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]]
6
example 2input → output
[[0,0,0,0,0,0,0,0]]
0
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    "4방향 연결"은 정확히 무엇을 의미하나요?
  • ☐
    여러 섬이 있을 때는 어떻게 하나요?
  • ☐
    방문한 셀을 추적해야 하는 이유는 무엇인가요?
  • ☐
    그리드를 직접 수정할 수 있나요?
  • ☐
    빈 그리드(크기 0)을 처리해야 하나요?
  • ☐
    대각선(8방향)도 연결로 간주해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 그리드 크기 초기화
○
ROWS, COLS = len(grid), len(grid[0])
○
ROWS = len(grid[0])
○
ROWS, COLS = len(grid), len(grid)
step 2· 방문 셀 추적용 집합 초기화
○
visit = set()
○
visit = []
○
visit = {}
step 3· DFS 함수: 경계 및 유효성 확인│ 중첩
○
if (
○
if r < 0 or r <= ROWS or c < 0 or c <= COLS:
○
if r < 0 or r == ROWS or c < 0 or c == COLS:
step 4· 현재 셀을 방문 집합에 추가│ 중첩
○
visit.add((r, c))
○
visit.remove((r, c))
○
if (r, c) not in visit: visit.add((r, c))
step 5· 4방향 재귀 탐색 및 넓이 누적│ 중첩
○
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
○
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1)
○
return max(1, dfs(r + 1, c), dfs(r - 1, c), dfs(r, c + 1), dfs(r, c - 1))
step 6· 모든 셀을 시작점으로 DFS 시도
○
for r in range(ROWS):
○
for r in range(1, ROWS):
    for c in range(1, COLS):
○
for r in ROWS:
    for c in COLS:
step 7· 최댓값 추적 및 반환│ │ 중첩
○
area = max(area, dfs(r, c))
○
area = dfs(r, c)
○
area += dfs(r, c)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
3
        ROWS, COLS = len(grid), len(grid[0])
4
        visit = set()
5
6
        def dfs(r, c):
7
            if (
8
                r < 0
9
                or r == ROWS
10
                or c < 0
11
                or c == COLS
12
                or grid[r][c] == 0
13
                or (r, c) in visit
14
            ):
15
                return 0
16
            visit.add((r, c))
17
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
18
19
        area = 0
20
        for r in range(ROWS):
21
            for c in range(COLS):
22
                area = max(area, dfs(r, c))
23
        return area
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[[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]]
→
6
case 2
[[0,0,0,0,0,0,0,0]]
→
0
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.