[리트코드/leetcode/python] 733. Flood Fill

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

이 문제는 전형적인 bfs,dfs 문제입니다.

문제 설명을 간단히 하자면, 주어진 image 그래프에서 (sr, sc) 위치에서부터 시작해 상,하,좌,우 4방향을 탐색하면서 image[sr][sc]와 값이 같다면, 해당 자리를 color 값으로 치환하는 문제입니다.

간단히 말해서, 시작하는 위치와 값이 같으면서 연결된 자리를 color 값으로 바꾸면 됩니다.

 

먼저, 코드를 살펴보면서 설명을 해보겠습니다.

import copy

class Solution(object):

    

    def floodFill(self,image, sr, sc, color):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type color: int
        :rtype: List[List[int]]
        """

        def search(image,r,c,value):
            
            paint[r][c] = True
            answer[r][c] = color

            for d in range(4):
                nr = r + dr[d] 
                nc = c + dc[d]
                if 0 <= nr < m and 0 <= nc < n:
                    if image[nr][nc] == value and paint[nr][nc] == False:
                        search(image,nr,nc,value)
                        
        answer = copy.deepcopy(image)

        dr = [-1,1,0,0]
        dc = [0,0,-1,1]

        m = len(image)
        n = len(image[0])

        paint = [[False] * n  for _ in range(m)]
        value = image[sr][sc]
        search(image,sr,sc,value)
 

        return answer

저는 재귀적으로 문제를 풀었는데요, 먼저 탐색을 위해 상하좌우를 할 때 행과 열의 움직임을 담은 배열 dr과 dc를 선언해줬습니다.

dr은 행이 상하좌우로 움직일 때, 칸 이동이 되는 숫자이고, dc는 열이 상하좌우로 움직일 때, 칸이 이동하는 숫자입니다.

paint 배열은 image와 크기가 같으며 처음에는 모두 False 값을 가지는 2차원 배열인데요, 저는 이 paint배열에서 값이 True가 되는 위치만 color로 변환해주려고 합니다. 

value는 image[sr][sc] 값이고, search함수를 탑니다.

 

search함수를 탄다면, 바로 paint[r][c] 값을 True로 바꿔주고, 기존에 image배열을 깊은 복사한 answer배열의 위치를 color값으로 바꿔줍니다. 먼저, True값으로 바뀌는 위치를 찾고 for문을 통해 image배열 자체를 color값을 가지는 배열로 바꿔도 되지만, 저는 동시에 이 작업을 해주기 위해 따로 처음에 deepcopy를 통한 깊은복사 작업을 진행했습니다.

 

search를 통해 들어온, 행과 열을 기준으로 (동,서,남,북) 4방향으로 탐색을 시작하는데요, 이 때 해당 위치가 범위내에 있는지와 해당 위치의 값이 image[sr][sc]과 같은지 그리고 paint[r][c]의 값이 Fasle로 아직 탐색하지 않은 위치일 때만 탐색합니다.

 

이렇게 재귀적으로 탐색을 끝내다보면, paint 배열은 color값으로 바뀌어야 하는 부분만 True로 되어있고, answer배열에서도 paint배열이 True인 부분만 color값을 가지게 됩니다.

 

리트코드에 있는 다른 코드도 한 번 살펴보시죠!

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type color: int
        :rtype: List[List[int]]
        """
        color = image[sr][sc]
        if color != newColor:
            image = self.fill(image, sr, sc, newColor, color)
        return image

    def fill(self, image, sr, sc, newColor, color):
        if 0 <= sr < len(image) and 0 <= sc < len(image[0]):
            if image[sr][sc] == color:
                image[sr][sc] = newColor
                
                image = self.fill(image, sr - 1, sc, newColor, color)
                image = self.fill(image, sr, sc + 1, newColor, color)
                image = self.fill(image, sr + 1, sc, newColor, color)
                image = self.fill(image, sr, sc - 1, newColor, color)
        
        return image

해당 코드도, 재귀적으로 함수를 타는 로직은 똑같습니다. DFS는 스택 또는 재귀함수로 구현하고 BFS는 큐를 이용해서 구현하는데, 이 둘을 잘 활용할 줄 알아야겠습니다.

 

이상 Flood Fill 문제를 정리해봤습니다.