Flood Fill

풀이

간단한 BFS문제이다

class Solution {
public:
    const int moveX[4] {-1,1,0,0};
    const int moveY[4] {0,0,-1,1};

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {

        int maxX = image.size();
        int maxY = image[0].size();

        bool visited[51][51] = {false};
        std::queue<pair<int,int>> q;
        int startColor = image[sr][sc];

        q.push(make_pair(sr,sc));
        visited[sr][sc] = true;

        while(q.size() > 0)
        {
            auto srsc = q.front();
            q.pop();

            int x = srsc.first;
            int y = srsc.second;
            image[x][y] = color;

            for(int i = 0; i < 4; i++)
            {
                int mx = x + moveX[i];
                int my = y + moveY[i];

                if (mx < 0 || mx >= maxX || 
                my < 0 || my >= maxY || 
                visited[mx][my] == true || 
                image[mx][my] != startColor) continue;

                visited[mx][my] = true;
                q.push(make_pair(mx,my));
            }
        }

        return image;
    }
};

이렇게 코드를 작성했는데

뭔가... 공간복잡도가 맘에 안들음

그래서 최적화를 고민해봄

먼저 핵심은 2가지임

1. startColor가 제공되는 color와 같으면 startColor의 주변 타일은 볼 필요도 없이 바로 return가능
2. 따라서 visited는 startColor != color인 타일만 찾으면 되므로 필요가 없음

예를들어

1	2	1
0	1	0
1	1	0

이런 타일이 있을때,

주어진 좌표가 1,1에 color가 1이라고 해보자

이미 주어진 좌표는 color와 같은 색상인 1이다.

따라서 주어진 좌표 주변에 같은 색상을 가지는 좌표가 있다고 하더라도
주어진 좌표와 색상이 동일하므로,
바로 return을 때릴수 있는것임

개선된 코드

class Solution {
public:
    const int moveX[4] {-1,1,0,0};
    const int moveY[4] {0,0,-1,1};

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {

        if(image[sr][sc] == color) return image;

        int maxX = image.size();
        int maxY = image[0].size();

        std::queue<pair<int,int>> q;
        int startColor = image[sr][sc];

        q.push(make_pair(sr,sc));

        while(q.size() > 0)
        {
            auto srsc = q.front();
            q.pop();

            int x = srsc.first;
            int y = srsc.second;
            image[x][y] = color;

            for(int i = 0; i < 4; i++)
            {
                int mx = x + moveX[i];
                int my = y + moveY[i];

                if (mx < 0 || mx >= maxX || 
                my < 0 || my >= maxY || 
                image[mx][my] != startColor) continue;

                q.push(make_pair(mx,my));
            }
        }

        return image;
    }
};

이 됨

BFS말고 재귀로 해결

class Solution {
public:
    void fill(std::vector<std::vector<int>>& image, int sr, int sc, int color, int newColor) {
        if (sr < 0 || sr >= image.size() || sc < 0 || sc >= image[0].size() || 
            image[sr][sc] != color || image[sr][sc] == newColor) {
            return;
        }

        image[sr][sc] = newColor;

        fill(image, sr - 1, sc, color, newColor);
        fill(image, sr + 1, sc, color, newColor);
        fill(image, sr, sc - 1, color, newColor);
        fill(image, sr, sc + 1, color, newColor);
    }

    std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int color) {
        fill(image, sr, sc, image[sr][sc], color);
        return std::move(image);
    }
};

이렇게 재귀를 이용한 재귀로 해결할수도 있음

더빠르고, 공간복잡도 최상ㅇㅇ