LeetCode [733]: Flood Fill

📌 LeetCode [733]: Flood Fill

🔗 문제 링크

---

문제 설명 📄

2D 배열 image가 주어지며, 배열의 픽셀 중 (sr, sc)의 위치에서 시작하여 해당 픽셀과 동일한 색상을 가진 모든 연결된 영역을 새 색상 color로 변경해야 합니다.

---

문제 접근 방식 📋

• 시작 픽셀 확인:
  • 주어진 (sr, sc) 픽셀의 색상(before)을 저장하고, 이를 color로 변경해야 합니다.
  • 만약 시작 픽셀의 색상이 이미 color라면 작업이 필요 없으므로 그대로 반환합니다.
• BFS 방식:
  • 큐(deque)를 사용하여 시작 픽셀부터 상하좌우로 확장하며 동일한 색상을 가진 모든 픽셀을 탐색합니다.
  • 방문한 픽셀은 즉시 color로 변경하여 중복 탐색을 방지합니다.

---

Solution 💻

from collections import deque

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        q = deque()
        if image[sr][sc] != color:
            q.append((sr, sc))
        before = image[sr][sc]

        while q:
            x, y = q.popleft()
            image[x][y] = color

            for px, py in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                dx, dy = x + px, y + py
                if 0 <= dx < len(image) and 0 <= dy < len(image[0]):
                    if image[dx][dy] == before:
                        q.append((dx, dy))

        return image

시간 복잡도 분석 ⏲️

• BFS 탐색: (O(m × n))
  • 이미지의 크기(픽셀 수)가 (m \times n)일 때, 모든 픽셀을 한 번씩 방문.
• 총 시간 복잡도: (O(m × n)).

공간 복잡도 분석 🗄️

• 큐 공간: (O(m × n))
  • 최악의 경우 모든 픽셀이 큐에 들어갈 수 있음.
• 총 공간 복잡도: (O(m × n)).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        def dfs(x, y):
            if not (0 <= x < len(image) and 0 <= y < len(image[0])) or image[x][y] != before:
                return
            image[x][y] = color
            for px, py in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                dfs(x + px, y + py)

        before = image[sr][sc]
        if before != color:
            dfs(sr, sc)

        return image

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

• DFS 탐색: (O(m × n))
  • 모든 픽셀을 한 번씩 방문.
• 총 시간 복잡도: (O(m × n)).

리팩토링 후 공간 복잡도 🗄️

• 재귀 호출 스택: (O(m × n))
  • 최악의 경우 재귀 호출이 모든 픽셀을 방문.
• 총 공간 복잡도: (O(m × n)).

---