[Programmers] FloodFill

문제 설명

n x m 크기 도화지에 그려진 그림의 색깔이 2차원 리스트로 주어집니다. 같은 색깔은 같은 숫자로 나타난다고 할 때, 그림에 있는 영역은 총 몇 개인지 알아내려 합니다. 영역이란 상하좌우로 연결된 같은 색상의 공간을 말합니다.

예를 들어, [[1,2,3], [3,2,1]] 같은 리스트는 다음과 같이 표현할 수 있습니다.

이때, 이 그림에는 총 5개 영역이 있습니다.

도화지의 크기 n과 m, 도화지에 칠한 색깔 image가 주어질 때, 그림에서 영역이 몇 개 있는지 리턴하는 solution 함수를 작성해주세요.

제한 사항

• n과 m은 1 이상 250 이하인 정수입니다.
• 그림의 색깔은 1 이상 30000 미만인 정수로만 주어집니다.

생각

bfs로 풀수도 있지만 dfs 푸는것을 연습해보자 아래와 같이 풀었다. 또한 FloodFill 에서는 DFS 풀이가 직관적이라고 생각한다. 방문영역을 체크한다음 재귀적으로 영역을 카운트했다. 이때 recursionlimit을 제한하지 않으면 에러가 발생한다🤦‍♂️

Python code

import sys
sys.setrecursionlimit(100000)
directions = [(1,0), (-1,0), (0,1), (0,-1)]
def dfs(n,m,y,x,image):
    check[y][x] = True
    for dy,dx in directions:
        ny = y + dy
        nx = x + dx 
        if 0<=ny<n and 0<=nx<m:
            if image[ny][nx] == image[y][x] and not check[ny][nx]:
                dfs(n,m,ny,nx,image)

def solution(n, m, image):
    cnt = 0
    global check
    check = [[False]*m for _ in range(n)]

    for y in range(n):
        for x in range(m):
            if not check[y][x]:
                cnt += 1
                dfs(n,m,y,x,image)
    return cnt