Leetcode - 733. Flood Fill

문제

mxn 2차원 map이 주어진다. 전달된 (sr, sc) 좌표의 값과 동일한 값을 가진 주변 요소를 모두 color값으로 바꿔라. (주변은 상하좌우 4방향을 의미한다)

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]]

해결 O(n) / O(n)

2차원 좌표 dfs, 그리고 visited 체크.

class Solution {
    int rsize;
    int csize;
    int **visited;
    void expanding(vector<vector<int>>& image, int sr, int sc, int from_c, int to_c) {
        if (sr < 0 || sr >= rsize)
            return;
        if (sc < 0 || sc >= csize)
            return;
        if (visited[sr][sc] == 1)
            return;
        if (image[sr][sc] != from_c)
            return;
            
        if (image[sr][sc] == from_c) {
            image[sr][sc] = to_c;
        }
        visited[sr][sc] = 1;
        expanding(image, sr-1, sc, from_c, to_c);
        expanding(image, sr+1, sc, from_c, to_c);
        expanding(image, sr, sc-1, from_c, to_c);
        expanding(image, sr, sc+1, from_c, to_c);
    }
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int from_color = image[sr][sc];
        rsize = image.size();
        csize = image[0].size();
        visited = (int **)calloc(rsize, sizeof(int *));
        for (int i = 0; i < rsize; i++)
            visited[i] = (int *)calloc(csize, sizeof(int));
        
        expanding(image, sr, sc, from_color, color);
        return image;
    }
};