[TIL]Day 167

FloodFill 문제에 대한 2가지 풀이법

기존에 프로그래머스에서 이 문제를 재귀로 풀었고 그래서 앞에 다음과 같이 재귀함수 호출 제한을 푸는 코드를 추가해서 문제를 풀었다.

import sys
sys.setrecursionlimit(30000)

def solution(n, m, image):
    answer = 0
    for i in range(n):
        for j in range(m):
            if image[i][j] != 0:
                answer += 1 
                area_check(image[i][j],i,j,n-1,m-1,image)
    return answer

def area_check(t,i,j,n,m,image):
    image[i][j] = 0
    #상
    if 0 <= i-1 <=n and image[i-1][j] == t:
        area_check(t,i-1,j,n,m,image)
    #하
    if i+1 <= n and image[i+1][j] == t:
        area_check(t,i+1,j,n,m,image)
    #좌
    if 0 <= j-1 <= m and image[i][j-1] == t:
        area_check(t,i,j-1,n,m,image)
    #우
    if j+1 <= m and image[i][j+1] == t:
        area_check(t,i,j+1,n,m,image)

리트코드에도 해당 문제가 있어서(733번)
이번에는 DFS로 접근하여 해결하였다.

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        oldColor = image[sr][sc]
        seen = set((sr,sc))
        stack = [(sr,sc)]
        
        while stack:
            r,c = stack.pop()
            image[r][c] = newColor
            
            rechargable = [(r,c-1),(r-1,c),(r,c+1),(r+1,c)]
            rechargable = [item for item in rechargable if item[0] >=0 and item[1] >= 0 and item[0]<len(image) and item[1] < len(image[0]) and image[item[0]][item[1]] == oldColor]
            
            for r,c in rechargable:
                if (r,c) not in seen:
                    stack.append((r,c))
                    seen.add((r,c))
        return image