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

다른 사람의 풀이

  • BFS 알고리즘을 사용해야 한다.
  • 현재 좌표에서 방문할 수 있는 다음 좌표를 확인하고, 그 다음 좌표에서 다시 방문할 수 있는 다음 좌표를 확인하는 것을 반복한다.
from collections import deque

def bfs(n, m, x, y, image, visited):
    queue = deque()
    queue.append([x, y])
    
    while len(queue) > 0:
        x, y = queue.popleft()
        deltas = [[0, 1], [0, -1], [1, 0], [-1, 0]] # x와 y 값의 변화량
        for [dx, dy] in deltas:
            next_x, next_y = x + dx, y + dy # 현재 좌표로부터 방문할 수 있는 다음 좌표
            if 0 <= next_x < n and 0 <= next_y < m and not visited[next_x][next_y] and image[x][y] == image[next_x][next_y]:
                visited[next_x][next_y] = True
                queue.append([next_x, next_y]) # 그 다음 좌표로부터 방문할 수 있는 다음 좌표를 확인하기 위해 큐에 넣는다
                

def solution(n, m, image):
    answer = 0
    visited = [[False] * m for _ in range(n)] # 방문한 좌표
    
    for i in range(n):
        for j in range(m):
            if not visited[i][j]:
                answer += 1
                visited[i][j] = True
                bfs(n, m, i, j, image, visited)
    return answer