[leetcode] 733. Flood Fill

문제 : https://leetcode.com/problems/flood-fill/description/

Solution

인자로 받은 위치의 번호로부터 시작하여 4방향으로 인접한 위치에 같은 번호가 있을 경우 번호들을 모두 다른 값으로 바꾸는 문제이다. Flood Fill이라는 이름답게 이동할 수 있는 모든 위치를 찾는 문제가 보면 된다.

#include <iostream>
#include <vector>
#include <queue>

class Solution
{
public:
    // 인자로 2차원 배열, 시작 위치(sr, sc), 변경하고자하는 색상 을 받는다.
    // 시작 위치에 있는 색상과 인접한 같은 색상을 인자로 받은 색상으로 변경하고, 변경된 2차원 배열을 반환하는 문제이다. 
    std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int color)
    {
        // 풀이 방법은 2차원에서 인접한 방향(4 또는 8 방향)으로 움직이며 자신과 같은 모든 번호를 찾아 변경하면 된다.
        // 또한 한번 확인한 인덱스는 굳이 다시 확인할 필요가 없으니 이동할 위치의 인덱스가 바뀐 인덱스라면 넘어간다.
        // 방식은 2가지가 있는데, DFS를 사용한 재귀, BFS를 사용한 큐 방식이다.


        // 인자로 받은 image의 중복 이동 방지를 위해 복사한다.
        // 이후 모든 요소를 0으로 초기화한다.
        copiedImage = image;
        for (auto& row : copiedImage) {
            std::fill(row.begin(), row.end(), 0);
        }

        // 1. DFS를 사용한 재귀 방식
        //CheckAdjacentIndexRecursive(image, sc, sr, color, image[sr][sc]);


        // 2. BFS를 사용한 큐 방식
        //CheckAdjacentIndexQueue(image, sc, sr, color, image[sr][sc]);

        return image;
    }

    // 인자로 받은 배열에서 현재 위치 기준 상하좌우를 확인하여 같은 색상이라면 색상을 바꾸는 함수
    void CheckAdjacentIndexRecursive(std::vector<std::vector<int>>& image, int x, int y, int color, int originalColor)
    {
        // 세로 길이 확인
        if (image.empty() || y < 0 || y >= image.size())
            return;

        // 가로 길이 확인
        if (image[0].empty() || x < 0 || x >= image[0].size())
            return;

        // 만약 현재 위치에 있는 색상이 originalColor라면
        if (copiedImage[y][x] != 1 && image[y][x] == originalColor)
        {
            // 색상을 바꾸고, 이동했다는 표시를 남긴다.
            image[y][x] = color;
            copiedImage[y][x] = 1;

            CheckAdjacentIndexRecursive(image, x, y - 1, color, originalColor);  // 상
            CheckAdjacentIndexRecursive(image, x, y + 1, color, originalColor);  // 하
            CheckAdjacentIndexRecursive(image, x - 1, y, color, originalColor);  // 좌
            CheckAdjacentIndexRecursive(image, x + 1, y, color, originalColor);  // 우
        }
    }

    // 인자로 받은 배열에서 현재 위치 기준 상하좌우를 확인하여 같은 색상이라면 색상을 바꾸는 함수
    void CheckAdjacentIndexQueue(std::vector<std::vector<int>>& image, int x, int y, int color, int originalColor)
    {
        q.push(std::make_pair(x, y));

        while (!q.empty())
        {
            const auto& index = q.front();
            x = index.first;
            y = index.second;

            if (
                y < 0 || y >= image.size() ||   // 세로 위치 확인
                x < 0 || x >= image[0].size()   // 가로 위치 확인
                )
            {
                ;
            }
            else
            {
                // 만약 현재 위치에 있는 색상이 originalColor라면
                if (copiedImage[y][x] != 1 && image[y][x] == originalColor)
                {
                    // 색상을 바꾸고, 이동했다는 표시를 남긴다.
                    image[y][x] = color;
                    copiedImage[y][x] = 1;

                    // 확인해야하는 위치 넣기
                    q.push(std::make_pair(x, y - 1));   // 상
                    q.push(std::make_pair(x, y + 1));   // 하
                    q.push(std::make_pair(x - 1, y));   // 좌
                    q.push(std::make_pair(x + 1, y));   // 우
                }
            }

            // 현재 위치 확인했으니 넘김
            q.pop();

        }
    }

private:
    std::vector<std::vector<int>> copiedImage;
    std::queue<std::pair<int, int>> q;
};



int main() {
    std::vector<std::vector<int>> image = { {0,0,0},{1,0,0} };
    Solution sol;
    sol.floodFill(image, 1, 0, 2);

    for (int i = 0; i < image.size(); ++i)
    {
        for (int j = 0; j < image[0].size(); ++j)
        {
            std::cout << image[i][j] << " ";
        }
        std::cout << "\n";
    }

    return 0;
}

 

예제는 주석 처리되어 있는 부분을 활성화시키면 된다.

// 1. DFS를 사용한 재귀 방식
//CheckAdjacentIndexRecursive(image, sc, sr, color, image[sr][sc]);


// 2. BFS를 사용한 큐 방식
//CheckAdjacentIndexQueue(image, sc, sr, color, image[sr][sc]);

 

이 문제의 시간 복잡도는 O(N * M)인데, 이는 2차원 배열에서 이동할 수 있는 모든 위치에 한번씩 이동하기 때문이다.

공간 복잡도 또한 O(N * M)인데, BFS(queue) 방식이던, DFS(재귀) 방식이던 최악의 경우 2차원 배열의 모든 위치에 접근하기 때문이다. 

 

Submission Detail

DFS : https://leetcode.com/submissions/detail/1531681396/

BFS : https://leetcode.com/submissions/detail/1531695553/