[Python / 알고리즘] Flood Fill 알고리즘

Flood Fill 알고리즘

• Flood Fill 알고리즘은 다차원 배열에서 특정 영역을 탐색하고 색을 채우기 위해 사용되는 알고리즘이다.
• 이 알고리즘은 주어진 시작점에서 인접한 같은 색의 영역을 탐색하며 색을 채운다.
• 탐색 과정에서 DFS나 BFS를 사용하여 인접 영역을 방문한다.
• 주로 픽셀 기반의 이미지 처리나 그래프 탐색 문제를 해결하는 데 활용된다.
• 시간복잡도: 배열의 행 수가 n, 열 수가 m 일때, O(n * m)

Flood Fill 알고리즘 구현

1. 먼저 시작 위치와 목표 색을 입력받고, 시작 위치의 기존 색을 확인한다.
2. 만약 시작 위치의 색과 목표 색이 동일하다면, 동작을 종료한다.
3. 시작 위치와 목표 색과 다르다면 목표 색으로 변경하고 상하좌우 인접한 영역을 탐색한다.
4. 인접 영역의 색이 기존 색과 동일할 때, 해당 위치로 이동하여 목표 색으로 변경하는 과정을 반복한다.

def flood_fill(x, y, target_color):
    original_color = matrix[x][y]
    
    # 기존 색과 목표 색이 동일하면 종료
    if original_color == target_color:
        return

    # 시작 위치의 색을 목표 색으로 변경
    matrix[x][y] = target_color
    stack = [(x, y)]

    while stack:
        cur_x, cur_y = stack.pop()
        
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = cur_x + dx, cur_y + dy
            
            # 범위 내에 있고, 동일한 색상인지 확인
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if matrix[nx][ny] != original_color:
                continue
            
            # 색상 변경
            matrix[nx][ny] = target_color
            
            # 상하좌우 인접 영역을 스택에 추가
            stack.append((nx, ny))

# 예제 행렬 및 크기 설정
matrix = [
    [1, 1, 1, 0],
    [1, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 0, 1, 1]
]
n, m = 4, 4

flood_fill(0, 0, 2)  # (0, 0) 위치에서 시작해 색을 2로 변경

# 결과 출력
for row in matrix:
    print(row)