Flood Fill | 알고달레

LeetCode의 733번째 문제인 Flood Fill를 함께 풀어보도록 하겠습니다.

문제

이미지 하나가 m x n 정수 행렬로 표현되고, image[i][j]는 이미지 내 픽셀(pixel) 값을 나타냅니다. 세개의 정수, sr과 sc 그리고 color가 주어졌을 때, image[sr][sc]부터 시작해서 Flood Fill 작업을 수행하시오.

여기서 Flood Fill이란 시작 픽셀과 값이 동일한 4방향으로 연결된 픽셀들, 그리고 그 픽셀들과 값이 동일한 4방형으로 연결된 픽셀들을, 그리고 또… 모두 같은 색상으로 변경하는 작업을 의미합니다.

Flood Fill 작업을 수행하여 변경된 이미지를 반환하시오.

예제

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]

풀이 1

주어진 이미지 내의 픽셀을 정점(Vertex, Node)으로 보고, 동일한 색상을 가진 픽셀들이 간선(Edge)으로 연결되어 있다고 생각하면 이 문제는 그래프(Graph) 문제로 볼 수 있는데요. 그러면 그래프 탐색을 통해서 주어진 좌표부터 동일한 색상의 픽셀을 찾아서 색상을 변경해줄 수 있을 것입니다.

그럼 각 좌표를 상하좌우 순으로 깊이 우선 탐색을 해볼까요?

우선 시작 좌표인 (1, 1)의 색상을 변경하고, 위에 있는 픽셀을 보면 색상이 동일합니다.

(1, 1), image[1][1] = 2
    - 상: (0, 1)

image = [
    [1, 1, 1],
    [1, 2, 0],
    [1, 0, 1]
]

그러므로 (0, 1)의 색상도 변경하고, 위를 보면 행렬의 범위를 벗어나는데요. 다음으로 아래를 보면 전 단계에서 이미 색상을 변경한 픽셀이고, 좌측에 동일한 색상의 픽셀이 있습니다.

(1, 1)
    - 상: (0, 1), image[0][1] = 2
        - 좌: (0, 0)

image = [
    [1, 2, 1],
    [1, 2, 0],
    [1, 0, 1]
]

(0, 0)의 색상을 변경하고, 위를 보면 행렬을 범위를 벗어나는데요. 다음으로 아래에 동일한 색상의 픽셀이 있습니다.

(1, 1)
    - 상: (0, 1)
        - 좌: (0, 0), image[0][0] = 2
            - 하: (1, 0)

image = [
    [2, 2, 1],
    [1, 2, 0],
    [1, 0, 1]
]

(1, 0)을 색상을 변경하고, 위를 보면 전 단계에서 변경한 픽셀이고, 아래에는 동일한 색상의 픽셀이 있습니다.

(1, 1)
    - 상: (0, 1)
        - 좌: (0, 0)
            - 하: (1, 0), image[1][0] = 2
                - 하: (2, 0)

image = [
    [2, 2, 1],
    [2, 2, 0],
    [1, 0, 1]
]

(2, 0)을 색상을 변경하고 주변을 보면 값이 1인 픽셀이 없습니다. (1, 0), (0, 0) 차례로 거슬러 올라가도 마찬가지 입니다. (0, 1)까지 올라가보면 우측에 값이 1인 픽셀이 있습니다.

(1, 1)
    - 상: (0, 1)
        - 좌: (0, 0) ✅
            - 하: (1, 0) ✅
                - 하: (2, 0), image[2][0] = 2 ✅
        - 우: (0, 2)

image = [
    [2, 2, 1],
    [2, 2, 0],
    [2, 0, 1]
]

(0, 2)을 2로 변경하고 주변을 보면 값이 1인 픽셀이 없습니다. 시작 좌표인 (1, 1)까지 거슬러 올라가도 더 이상 주변에 값이 1인 픽셀이 발견되지 않습니다.

(1, 1) ✅
    - 상: (0, 1) ✅
        - 좌: (0, 0) ✅
            - 하: (1, 0) ✅
                - 하: (2, 0) ✅
        - 우: (0, 2), image[2][0] = 2 ✅

image = [
    [2, 2, 2],
    [2, 2, 0],
    [2, 0, 1]
]

지금까지 설명드린 깊이 우선 탐색을 재귀 알고리즘을 사용하여 파이썬으로 구현해보겠습니다.

class Solution:
    def floodFill(
        self, image: List[List[int]], sr: int, sc: int, color: int
    ) -> List[List[int]]:
        if image[sr][sc] == color:
            return image

        old = image[sr][sc]

        def dfs(row, col):
            image[row][col] = color

            for r, c in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if 0 <= row + r < len(image) and 0 <= col + c < image[0]:
                    if image[row + r][col + c] == old:
                        dfs(row + r, col + c)

        dfs(sr, sc)
        return image

이미지 내의 픽셀 총 수를 n이라고 했을 때, 이 풀이의 시간 복잡도와 공간 복잡도는 모두 O(n)이 되는데요. 최악의 경우, 함수 호출 스택의 깊이가 n이 될 수 있기 때문입니다.

풀이 2

이번에는 큐(Queue)을 사용하여 너비 우선 탐색으로 이 문제에 접근해 보겠습니다.

기본 아이디어는 시작 좌표와 가까운 좌표의 픽셀 값을 멀리 있는 좌표의 픽셀 값보다 먼저 변경하는 것입니다.

시작 좌표에 있는 픽셀의 값을 주어진 색상으로 변경합니다.
시작 좌표에 인접하고 있는 좌표 중에서 색상이 동일한 픽셀의 값을 주어진 색상으로 변경합니다.
방금 색상을 변경한 픽셀에 인접하고 있는 좌표 중에서 색상이 동일한 픽셀의 값을 주어진 색상으로 연쇄적으로 변경합니다.

그러면 마치 호수에 돌을 던졌을 때처럼 시작 좌표부터 점점 밖으로 퍼져나가면서 이미지의 색상이 변경될 것입니다.

그럼 문제에서 주어진 첫 번째 예제로 함께 생각해볼까요?

우선 시작 좌표에 있는 픽셀의 값을 2로 변경하고, 시작 좌표를 큐에 추가합니다.

image[1][1] = 2
queue = [(1, 1)]
image = [
    [1, 1, 1],
    [1, 2, 0],
    [1, 0, 1]
]

큐에서 (1, 1)을 제거하고, 주변에 값이 1인 픽셀이 있는지 살핍니다. 위와 좌측의 색상을 변경하고, 각 좌표를 큐에 차례로 추가합니다.

(1, 1) 제거
위: image[0][1] = 2, (0, 1) 추가
좌: image[1][0] = 2, (1, 0) 추가

queue = [(0, 1), (1, 0)]
image = [
    [1, 2, 1],
    [2, 2, 0],
    [1, 0, 1]
]

큐에서 (0, 1)을 제거하고, 주변에 값이 1인 픽셀이 있는지 살핍니다. 좌우측의 색상을 변경하고, 각 좌표를 큐에 차례로 추가합니다.

(0, 1) 제거
좌: image[0][1] = 2, (0, 0) 추가
우: image[0][2] = 2, (0, 2) 추가

queue = [(1, 0), (0, 0), (0, 2)]
image = [
    [2, 2, 2],
    [2, 2, 0],
    [1, 0, 1]
]

큐에서 (1, 0)을 제거하고, 주변에 값이 1인 픽셀이 있는지 살핍니다. 위와 하단의 색상을 변경하고, 이 좌표를 큐에 차례로 추가합니다.

(1, 0) 제거
하: image[2][0] = 2, (2, 0) 추가

queue = [(0, 0), (0, 2), (2, 0)]
image = [
    [2, 2, 2],
    [2, 2, 0],
    [2, 0, 1]
]

큐에서 (0, 0)을 제거하고, 주변에 값이 1인 픽셀이 있는지 살핍니다. 주변에 값이 1인 픽셀이 없으므로, 아무 좌표도 큐에 추가하지 않습니다.

(0, 0) 제거

queue = [(0, 2), (2, 0)]
image = [
    [2, 2, 2],
    [2, 2, 0],
    [2, 0, 1]
]

큐에서 (0, 2)을 제거하고, 주변에 값이 1인 픽셀이 있는지 살핍니다. 주변에 값이 1인 픽셀이 없으므로, 아무 좌표도 큐에 추가하지 않습니다.

(0, 2) 제거

queue = [(2, 0)]
image = [
    [2, 2, 2],
    [2, 2, 0],
    [2, 0, 1]
]

큐에서 (2, 0)을 제거하고, 주변에 값이 1인 픽셀이 있는지 살핍니다. 주변에 값이 1인 픽셀이 없으므로, 아무 좌표도 큐에 추가하지 않습니다.

(2, 0) 제거

queue = []
image = [
    [2, 2, 2],
    [2, 2, 0],
    [2, 0, 1]
]

큐가 비었으므로 시작 픽셀과 동일한 색상의 픽셀을 모두 탐색했다는 뜻입니다. 이미지 행렬의 최종 모습이 우리가 원하던 모습과 일치합니다.

지금까지 설명드린 너비 우선 탐색 알고리즘을 파이썬으로 구현해보겠습니다.

from collections import deque


class Solution:
    def floodFill(
        self, image: List[List[int]], sr: int, sc: int, color: int
    ) -> List[List[int]]:
        if image[sr][sc] == color:
            return image

        old = image[sr][sc]

        image[sr][sc] = color
        queue = deque([(sr, sc)])

        while queue:
            row, col = queue.popleft()
            for r, c in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if 0 <= row + r < len(image) and 0 <= col + c < len(image[0]):
                    if image[row + r][col + c] == old:
                        image[row + r][col + c] = color
                        queue.append((row + r, col + c))
        return image

위 풀이와 동일하게 이 풀이의 시간 복잡도와 공간 복잡도도 모두 O(n)인데요. 너비 우선 탐색을 한다고 해서 연산량이나 메모리 사용량이 줄어들지는 않기 때문입니다.

마치면서

이 문제가 너무 어려우셨다면 비슷하지만 좀 더 쉬운 문제인 01 Matrix도 풀어보시라고 추천드립니다. 코딩 테스트에서 그래프를 어떻게 다루는지에 대해서 더 공부하고 싶으시다면 관련 게시물을 참고 바랄께요.