LeetCode [200]: Number of Islands

📌 LeetCode [200]: Number of Islands

🔗 문제 링크

---

문제 설명 📄

2D 그리드 맵이 주어질 때, '1'(육지)로 연결된 섬의 개수를 반환하는 문제입니다. 섬은 상하좌우로 연결된 '1'들로 구성됩니다. '0'(물)은 육지를 분리합니다.

---

문제 접근 방식 📋

1. BFS를 사용한 탐색:
   • 그리드의 모든 셀을 순회하며, 새로운 '1'을 발견할 때마다 BFS를 시작합니다.
   • BFS는 큐를 사용하여 인접한 모든 '1'을 탐색하고, 방문한 셀을 visited에 기록합니다.
2. 방문 기록:
   • 이미 방문한 셀은 다시 탐색하지 않도록 visited 집합을 사용하여 체크합니다.
3. 섬의 개수 계산:
   • 새로운 '1'을 발견할 때마다 섬의 개수를 증가시킵니다.

---

Solution 💻

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        q = deque()
        visited = set()
        rows = len(grid)
        cols = len(grid[0])
        answer = 0

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1" and (i, j) not in visited:
                    q.append((i, j))
                    visited.add((i, j))
                    answer += 1
                    while q:
                        x, y = q.popleft()
                        for px, py in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                            dx, dy = x + px, y + py
                            if 0 <= dx < rows and 0 <= dy < cols and (dx, dy) not in visited:
                                if grid[dx][dy] == "1":
                                    visited.add((dx, dy))
                                    q.append((dx, dy))
        return answer

---

시간 복잡도 분석 ⏲️

• 시간 복잡도:  (O(M×N))
  • 그리드의 각 셀을 최대 한 번 방문하므로, (M)은 행의 개수, (N)은 열의 개수일 때 전체 복잡도는 (O(M \times N))입니다.
• 공간 복잡도: (min(M,N))
  • 방문한 셀을 저장하기 위한 visited 집합 및 큐에 최대 (min(M,N)))의 공간이 필요합니다.

---

리팩토링 🛠️

개선된 코드

visited 집합을 제거하고, 입력 그리드 자체를 수정하여 방문 체크를 수행합니다.

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        q = deque()
        rows = len(grid)
        cols = len(grid[0])
        answer = 0

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    q.append((i, j))
                    grid[i][j] = "0"  # 방문 표시
                    answer += 1
                    while q:
                        x, y = q.popleft()
                        for px, py in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                            dx, dy = x + px, y + py
                            if 0 <= dx < rows and 0 <= dy < cols and grid[dx][dy] == "1":
                                grid[dx][dy] = "0"
                                q.append((dx, dy))
        return answer

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도: (O(M×N))
  • 동일하게 각 셀을 한 번만 방문합니다.
• 공간 복잡도: (min(M,N))
  • 큐의 크기는 섬의 크기에 비례하므로, 최악의 경우 한쪽 방향으로 긴 섬에서 큐가 (min(M,N)) 공간을 사용합니다.

---