733. Flood Fill

733. Flood Fill

 

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:        
        # (sr, sc) 시작으로. color 로 바꾸면 됨
        # 4방향으로 확산 => BFS => 큐 사용
        rows, cols = len(image), len(image[0])
        visited = set()
        q = deque([(sr, sc)])
        visited.add((sr, sc))
        start_val = image[sr][sc]

        while q:
            r, c = q.popleft()     
            rowInbounds = 0<= r and r< rows
            colInbounds = 0<= c and c< cols

            if not rowInbounds or not colInbounds: # 범위 안에 안들어오면
                continue       

            if image[r][c] != start_val:
                continue
            
            if (r, c) in visited:
                continue       

            visited.add((r, c))
            image[r][c] = color

            q.append((r-1, c))
            q.append((r+1, c))
            q.append((r, c-1))
            q.append((r, c+1))
        return image

 

좋아요! 거의 잘 짜셨지만, 지금 코드에서 생길 수 있는 주요 문제점이 하나 있어요.

---

❗ 핵심 이슈

visited.add((sr, sc))  # 초기 방문 추가

...

if (r, c) in visited:
    continue
visited.add((r, c))

• 이미 (sr, sc)를 visited에 넣었기 때문에 첫 반복에서 바로 continue에 걸려서 아무 동작도 하지 않게 됩니다.
• 결과적으로 시작 지점만 큐에 넣고 아무것도 색칠하지 않고 종료될 수 있어요.

---

✅ 해결 방법

• 큐에 넣기 전에 방문 여부를 체크하고 방문 등록까지 같이 해야 합니다.
  • visited 중복 체크는 큐에 넣기 전에 끝내야 해요.
• 그리고 큐에서 뺀 후엔 무조건 색칠해야 합니다.

 

수정된 내 코드

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:        
        # (sr, sc) 시작으로. color 로 바꾸면 됨
        # 4방향으로 확산 => BFS => 큐 사용
        rows, cols = len(image), len(image[0])
        visited = set()
        q = deque([(sr, sc)])
        visited.add((sr, sc))
        start_val = image[sr][sc]

        while q:
            r, c = q.popleft()     
            rowInbounds = 0<= r and r< rows
            colInbounds = 0<= c and c< cols

            if not rowInbounds or not colInbounds: # 범위 안에 안들어오면
                continue       

            if image[r][c] != start_val:
                continue

            image[r][c] = color            

            for dr, dc in [[1,0], [-1,0], [0,1], [0,-1]]:
                if (r+dr, c+dc) in visited:
                    continue       
                visited.add((r+dr, c+dc))
                q.append((r+dr, c+dc))
        return image

 

솔루션 (BFS)

from typing import List
from collections import deque

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        rows, cols = len(image), len(image[0])
        start_val = image[sr][sc]

        if start_val == color:
            return image  # 색이 같으면 처리할 필요 없음

        visited = set()
        q = deque([(sr, sc)])
        visited.add((sr, sc))

        while q:
            r, c = q.popleft()
            image[r][c] = color

            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                    if image[nr][nc] == start_val:
                        visited.add((nr, nc))
                        q.append((nr, nc))

        return image

 

솔루션 (DFS)

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        R, C = len(image), len(image[0])
        color = image[sr][sc]
        if color == newColor:
            return image
        def dfs(r, c):
            if image[r][c] == color:
                image[r][c] = newColor
                if r >= 1:
                    dfs(r-1, c)
                if r + 1 < R:
                    dfs(r + 1, c)
                if c >= 1:
                    dfs(r, c - 1)
                if c + 1 < C:
                    dfs(r, c + 1)

        dfs(sr, sc)
        return image

 

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        if image[sr][sc] == color:
            return image

        def dfs(r, c, visited, searchColor, color):
            rowInbounds = 0 <= r and r < len(image)  # <-- 주의 !!
            colInbounds = 0 <= c and c < len(image[0]) # <-- 주의 !!

            if not (rowInbounds and colInbounds): # <-- 주의 !!
                return
            if (r, c) in visited:
                return
            if image[r][c] != searchColor:
                return

            visited.add((r, c))
            image[r][c] = color

            dfs(r-1, c, visited, searchColor, color)
            dfs(r+1, c, visited, searchColor, color)
            dfs(r, c-1, visited, searchColor, color)
            dfs(r, c+1, visited, searchColor, color)

        dfs(sr, sc, set(), image[sr][sc], color)
        return image

 

최종 내 코드(BFS)

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        if image[sr][sc] == color:
            return image

        org_color = image[sr][sc]
        q = deque([(sr, sc)])
        visited = set()       

        while q:
            r, c = q.popleft()
            image[r][c] = color
            visited.add((r, c))

            for dr, dc in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                nr, nc = r+dr, c+dc
                if 0<= nr < len(image) and  0<= nc < len(image[0]) and (nr, nc) not in visited and image[nr][nc] == org_color:
                    q.append((nr, nc))
        return image

 

 

---

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        # (sr, sc) 시작해서 같은 value 를 가지면 color 로 바꾸고 퍼져나감
        if image[sr][sc] == color:
            return image

        origin_color = image[sr][sc]  # 비교를 위해, 원래 컬러값 저장

        # bfs 즉 큐로 해서 퍼져나가도 되고, dfs 재귀로 해도 됨
        # 1. bfs
        q = deque([(sr, sc)]) # 우선 시작점 추가
        visited = set()
        visited.add((sr, sc)) # 방문 추가

        while q:
            for _ in range(len(q)): # 사실 이 루프 필요없을듯!!
                r, c = q.popleft()
                image[r][c] = color # 컬러 값 바꾸고

                for dr, dc in [[1, 0], [-1,0], [0,1], [0,-1]]:
                    nr, nc = r+dr, c+dc
                    # 범위가 유효하고, 아직 방문 안했고, 변경해야할 값을 가지면
                    if 0<= nr and nr < len(image) and 0<=nc and nc <len(image[0]) and (nr, nc) not in visited and image[nr][nc] == origin_color:
                        # 큐 추가, visited 추가
                        q.append((nr, nc))
                        visited.add((nr, nc))

        return image