Lv3 FloodFill

문제

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

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

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

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

제한 사항

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

입출력 예

n	m	images	정답
2	3	[[1, 2, 3], [3, 2, 1]]	5
3	2	[[1, 2], [1, 2], [4, 5]]	4

입출력 예 #1

앞서 설명한 예와 같습니다.

입출력 예 #2

주어진 이미지는 다음과 같이 표현할 수 있습니다.

따라서 이 이미지에는 4개 영역이 있습니다.

풀이

재귀호출로 상하좌우를 탐색하는 방식으로 해결. 파이썬에서는 재귀호출 제한이 있어 미리 지정이 필요하다.

코드

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)