733. Flood Fill

733. Flood Fill

DFS/BFS 문제 시작!

기본적인 문제인데, 배운지 좀 되서 구현하는데 어려움이 있었다. 차근히 연습하면서 깎아보려고 한다.

from collections import deque

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original = image[sr][sc]
        if original == color:
            return image
        directions = [(0,1), (1,0), (-1,0), (0,-1)]
        queue = deque([(sr, sc)])
        image[sr][sc] = color
        while len(queue) != 0:
            sr, sc = queue.popleft()
            
            for dx, dy in directions:
                if 0 <= sr + dx < len(image) and 0 <= sc + dy < len(image[0]) and image[sr+dx][sc+dy] == original:
                    queue.append((sr+dx, sc+dy))
                    image[sr+dx][sc+dy] = color
        return image

deque를 이용한 BFS를 선호하는 편인데, recursion 대신 iteration을 이용해서 제한이 없기 때문이다.
그래도 연습삼아 DFS로도 풀어보았다. 개인적으로 구현 난이도는 DFS가 더 편하긴 하다ㅋㅋ

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        m = len(image)
        n = len(image[0])
        original = image[sr][sc]

        def dfs(x,y):
            if x < 0 or x >= m or y < 0 or y >= n or image[x][y] == color:
                return
            
            if image[x][y] == original:
                image[x][y] = color

                dfs(x-1,y)
                dfs(x+1,y)
                dfs(x,y-1)
                dfs(x,y+1)

        dfs(sr,sc)

        return image