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개 영역이 있습니다.

 

#코드

from collections import deque
 
def solution(n, m, image):
    answer  = 0  
    visited = [[0]*(m) for _ in range(n)]  
    cnt     = 0
    # 상, 하, 좌, 우
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]        
 
    deq = deque()
    def BFS(row, col):        
        
        deq.append((row, col))        
        
        while deq:
            row, col = deq.popleft()
            for i in range(4):
                ny = dy[i]+row
                nx = dx[i]+col
                if 0<=ny<n and 0<=nx<m and visited[ny][nx]==0:
                    if image[row][col] == image[ny][nx]:
                        visited[ny][nx]=cnt
                        deq.append((ny, nx))
            
        
    for i in range(len(image)):
        for j in range(len(image[i])): 
            if visited[i][j] == 0:
                cnt+=1
                visited[i][j]=cnt                
                BFS(i, j)
    
    answer = cnt
    return answer