← 전체 회차
a-080-number-of-islands2026-08-07mediumleetcode #200neetcode150

섬의 개수

#array#depth-first-search#breadth-first-search#union-find#matrix
↗ leetcode #200 · a-080-number-of-islands
01

문제

· problem
P.a-080-number-of-islands

섬의 개수

↗ leetcode #200

m × n 크기의 2D 이진 그리드가 주어집니다. 이 그리드에서 '1'은 땅, '0'은 물을 나타냅니다. 섬의 개수를 반환하세요. 섬은 물로 둘러싸여 있으며 인접한 땅들이 수평 또는 수직으로 연결되어 있습니다. 그리드의 모든 네 모서리는 물로 둘러싸여 있다고 가정할 수 있습니다.

제약
  • · 1 ≤ m, n ≤ 300
  • · grid[i][j] ∈ {'0', '1'}
  • · m == grid.length, n == grid[i].length
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
1
example 2input → output
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
3
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    인접한 셀은 무엇을 포함하나요?
  • ☐
    입력 그리드를 수정할 수 있나요?
  • ☐
    null이거나 빈 그리드를 어떻게 처리하나요?
  • ☐
    대각선으로 연결된 땅도 같은 섬으로 계산하나요?
  • ☐
    물(0)의 개수를 세어야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 엣지 케이스 확인
○
○
if len(grid) == 0: return 0
○
if grid is None: return -1
step 2· 자료 구조 초기화
○
○
islands = 1
○
visit = []
step 3· DFS 경계 및 상태 검사│ 중첩
○
○
if r < 0 or r >= rows or c < 0 or c >= cols: return
○
if grid[r][c] != '1': return
step 4· 방문 표시 및 4방향 탐색│ 중첩
○
○
visit.add((r, c)); dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1)
○
dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1); visit.add((r, c))
step 5· 주 반복문: 미방문 땅 셀 찾기
○
○
if grid[r][c] == '1':
○
if (r, c) not in visit:
step 6· 섬 카운터 증가 및 DFS 호출│ 중첩
○
○
dfs(r, c); islands += 1
○
islands = islands + 1 + count_connected_cells(r, c)
step 7· 결과 반환
○
○
return len(visit)
○
return islands + 1
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04
문제풀이 · 트레이스
· solve
solution.py
1
class Solution:
2
    def numIslands(self, grid: List[List[str]]) -> int:
3
        if not grid or not grid[0]:
4
            return 0
5
6
        islands = 0
7
        visit = set()
8
        rows, cols = len(grid), len(grid[0])
9
10
        def dfs(r, c):
11
            if (
12
                r not in range(rows)
13
                or c not in range(cols)
14
                or grid[r][c] == "0"
15
                or (r, c) in visit
16
            ):
17
                return
18
19
            visit.add((r, c))
20
            directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
21
            for dr, dc in directions:
22
                dfs(r + dr, c + dc)
23
24
        for r in range(rows):
25
            for c in range(cols):
26
                if grid[r][c] == "1" and (r, c) not in visit:
27
                    islands += 1
28
                    dfs(r, c)
29
        return islands
30
31
# DFS O(1) Space and much less code
32
class Solution:
33
    def numIslands(self, grid: List[List[str]]) -> int:
34
        rows, cols = len(grid), len(grid[0])
35
        def dfs(r, c):
36
            if not 0 <= r < len(grid) or not 0 <= c < len(grid[0]) or grid[r][c] == '0':
37
                return 0
38
            grid[r][c] = '0'
39
            dfs(r + 1, c)
40
            dfs(r - 1, c)
41
            dfs(r, c + 1)
42
            dfs(r, c - 1)
43
            return 1
44
        count = 0
45
        for r in range(rows):
46
            for c in range(cols):
47
                count += dfs(r, c)
48
        return count
49
50
# BFS Version From Video
51
class SolutionBFS:
52
    def numIslands(self, grid: List[List[str]]) -> int:
53
        if not grid:
54
            return 0
55
56
        rows, cols = len(grid), len(grid[0])
57
        visited = set()
58
        islands = 0
59
60
         def bfs(r, c):
61
             q = deque()
62
             visited.add((r, c))
63
             q.append((r, c))
64
           
65
             while q:
66
                 row, col = q.popleft()
67
                 directions = [[1, 0],[-1, 0],[0, 1],[0, -1]]
68
               
69
                 for dr, dc in directions:
70
                     r, c = row + dr, col + dc
71
                     if (r) in range(rows) and (c) in range(cols) and grid[r][c] == '1' and (r, c) not in visited:
72
                       
73
                         q.append((r, c ))
74
                         visited.add((r, c ))
75
76
         for r in range(rows):
77
             for c in range(cols):
78
               
79
                 if grid[r][c] == "1" and (r, c) not in visited:
80
                     bfs(r, c)
81
                     islands += 1 
82
83
         return islands
84
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
→
1
case 2
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
→
3
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.