[프로그래머스] FloodFill python

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

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

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

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

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


  1. BFS를 사용해서 이미지를 탐색한다.
  2. 탐색한 위치를 visited에 체크하고 큐에 넣어준다.
  3. 큐를 모두 pop하면 카운트를 증가시킨다.
from collections import deque
def solution(n, m, image):
    cnt = 0
    visited = [[False] * m for _ in range(n)]
    dir = [[1,0], [0,1], [-1,0], [0,-1]]
    for i in range(n):
        for j in range(m):
            if not visited[i][j]:
                q = deque()
                q.append([i,j])
                visited[i][j] = True
                color = image[i][j]
                while q:
                    y, x = q.popleft()
                    for dy, dx in dir:
                        yy, xx = y+dy, x+dx
                        if 0 <= yy < n and 0 <= xx < m:
                            if not visited[yy][xx]:
                                if image[yy][xx] == color:
                                    visited[yy][xx] = True
                                    q.append([yy,xx])
                cnt += 1
    return cnt

좋은 웹페이지 즐겨찾기