FloodFill (python)

전형적인 BFS문제, 필수로 알고 있어야 하는 유형, 많은 문제 응용 됨

👀 깃헙 소스

문제설명

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

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

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

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

입출력 예

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

솔루션
좌표를 0,0부터 n,m까지 순회하면서 방문되지 않은 노드를 확인한다.
BFS를 진행하면서 같은 색을가진 인접 노드를 방문처리 해준다.

코드

# 파이썬
from collections import deque

def visitable(n, m, y, x):
    return 0 <= y < n and 0 <= x < m

def solution(n, m, image):
    visited, bfs_nodes = set(), deque([])
    DELTAS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    answer = 0
    
    for y in range(n):
        for x in range(m):
            if (y, x) in visited:
                continue
            answer +=1
            bfs_nodes.append((y, x))
            visited.add((y, x))

            while bfs_nodes:
                cur_y, cur_x = bfs_nodes.popleft()
                for dx, dy in DELTAS:
                    next_y, next_x = cur_y + dy, cur_x + dx
                    if visitable(n, m, next_y, next_x) and \
                    (next_y, next_x) not in visited and \
                    image[cur_y][cur_x] == image[next_y][next_x]:
                        bfs_nodes.append((next_y, next_x))
                        visited.add((next_y, next_x))
                    
    return answer