leetcode 733. Flood Fill 풀이

문제 : 아래와 같이 최초의 좌표로 부터 같은 값을 가지는 상하좌우에 대해 newColor를 전개한 후 image를 반환하라

 

Input: image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 Output: [[2,2,2],[2,2,0],[2,0,1]]

Follow up :

 

아이디어 : floodfill 에 대한 기본적인 문제로 상하좌우를 순회하며 index를 넘어가지 않으면서 값을 전개한다.

 

코드 :

 

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])
        visit = [[0 for i in range(m)] for j in range(n)]
        s = []
        dr = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        s.append([sr, sc])
        visit[sr][sc] = 1
        #print(image)
        while s:
            tr, tc = s.pop()
            ori = image[tr][tc]
            image[tr][tc] = newColor
            for d in dr:
                nr = tr + d[0]
                nc = tc + d[1]
                if nr < 0 or n <= nr:
                    continue
                if nc < 0 or m <= nc:
                    continue
                if visit[nr][nc] == 0 and ori == image[nr][nc]:
                    visit[nr][nc] = 1
                    s.append([nr,nc])
        return image

 

학습 포인트 : floodfill에 대한 기본을 다시 한번 다질 수 있는 기회였다.

 

출처 : leetcode.com/problems/flood-fill/