[LeetCode] 773. Flood Fill

[LeetCode] 773. Flood Fill

 

DFS 로 풀 수 있는 문제이다.

 

나의 풀이

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        
        n = len(image)
        m = len(image[0])
        visited = [[0] * m for _ in range(n)];
        dx = [1,-1,0,0]
        dy = [0,0,1,-1]
        
        def dfs(r,c, targetColor, newColor):
            for _ in range(4):
                newR = r + dy[_]
                newC = c + dx[_]
                
                if (newR < 0 or newR >= n or newC < 0 or newC >= m or visited[newR][newC] or image[newR][newC] != targetColor):
                    continue;
                image[newR][newC] = newColor
                visited[newR][newC] = 1
                dfs(newR, newC, targetColor, newColor)
        
        targetColor = image[sr][sc]
        dfs(sr,sc, targetColor, newColor);
        image[sr][sc] = newColor
        
        return image

다른 사람의 더 간단명료한 풀이

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        self.dfs(image, sr, sc, image[sr][sc], newColor)
        return image
    def dfs(self, image, m, n, oldValue, newValue):
        if m < 0 or m > len(image)-1 or n < 0 or n > len(image[0])-1 or image[m][n] == newValue:
            return
        if image[m][n] == oldValue:
            image[m][n] = newValue
            self.dfs(image, m-1, n, oldValue, newValue)
            self.dfs(image, m+1, n, oldValue, newValue)
            self.dfs(image, m, n-1, oldValue, newValue)
            self.dfs(image, m, n+1, oldValue, newValue)
        return