[leetcode] 733. Flood Fill - Python

🔍 Problem

https://leetcode.com/problems/flood-fill/

---

📰 문제풀이

• 제한 시간: 20분
• 성공 여부: 실패
• 실패 원인: 문제에서 원하는 솔루션 조건을 이해하지 못했다...

---

📃 Solving Process

1. starting pixel과 color의 색깔이 달라야 한다.
2. 색깔이 다르다면 이제 starting pixcel과 같은 색이고 image 내에서 방문할 수 있는 지역이라면 해당 pixel의 색깔을 color로 바꿔준다.

---

💻 Code

from collections import deque


class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        origin_color = image[sr][sc]
        row, col = len(image), len(image[0])

        if origin_color != color:
            queue = deque()
            queue.append([sr, sc])

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

                for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if 0 <= nx < row and 0 <= ny < col and image[nx][ny] == origin_color:
                        queue.append((nx, ny))
        return image

---

⏱ Time Complexity

• 탐색 가능한 pixel을 모두 방문해야 돼서 최대 O(N)만큼의 시간 복잡도가 소요된다.

---

💾 Space Complexity

• 방문해야 하는 노드의 정보를 queue에 계속 담기 때문에 O(N)만큼의 공간 복잡도가 필요하다.