FloodFill 유형 문제 분석

1. 벽과 문 거리 계산

문제 설명:

2D 그리드에서 방 상태를 나타내는 rooms 배열이 주어집니다. 각 셀은 벽(-1), 문(0), 빈 방(2³¹-1) 중 하나입니다. 모든 빈 방에 대해 가장 가까운 문까지의 거리를 계산하세요.

제약 조건:

• m == rooms.length
• n == rooms[i].length
• 1 ≤ m, n ≤ 250

해결 전략:

모든 문의 위치를 큐에 초기 삽입합니다. BFS를 수행하며 인접한 빈 방의 거리를 현재 셀 값 +1로 업데이트합니다. 업데이트된 빈 방은 다시 큐에 추가되어 주변 셀 전파를 계속합니다.

class GridSolver {
    const int dirs[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
public:
    void computeDistances(vector<vector<int>>& grid) {
        queue<pair<int, int>> bfsQueue;
        int rows = grid.size();
        int cols = grid[0].size();
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 0) bfsQueue.push({r, c});
            }
        }
        
        while (!bfsQueue.empty()) {
            auto [curR, curC] = bfsQueue.front();
            bfsQueue.pop();
            for (const auto& d : dirs) {
                int nextR = curR + d[0];
                int nextC = curC + d[1];
                if (nextR < 0 || nextR >= rows || nextC < 0 || nextC >= cols) continue;
                if (grid[nextR][nextC] == INT_MAX) {
                    grid[nextR][nextC] = grid[curR][curC] + 1;
                    bfsQueue.push({nextR, nextC});
                }
            }
        }
    }
};

성능 분석:

• 시간 복잡도: O(rows×cols)
• 공간 복잡도: O(rows×cols)

2. 영역 채색 알고리즘

문제 설명:

이미지를 표현하는 2D 배열과 시작 위치(sr,sc), 새 색상이 주어집니다. 시작점과 색상이 같은 연결된 영역을 모두 새로운 색상으로 변경하세요.

예시:

입력: 
image = [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, newColor=2
출력: 
[[2,2,2],[2,2,0],[2,0,1]]

제약 조건:

• 1 ≤ image.length, image[0].length ≤ 50
• 0 ≤ image[i][j], newColor ≤ 65535

해결 전략:

BFS를 사용해 시작점과 동일한 색상을 가진 인접 셀을 탐색합니다. 탐색된 셀은 즉시 새 색상으로 변경하고 큐에 추가하여 인접 영역을 계속 탐색합니다.

class ImagePainter {
    const int moves[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    
    void fillArea(vector<vector<int>>& img, int startR, int startC, int newCol) {
        queue<pair<int, int>> pixelQueue;
        int original = img[startR][startC];
        if (original == newCol) return;
        
        pixelQueue.push({startR, startC});
        img[startR][startC] = newCol;
        int height = img.size();
        int width = img[0].size();
        
        while (!pixelQueue.empty()) {
            auto [r, c] = pixelQueue.front();
            pixelQueue.pop();
            for (const auto& m : moves) {
                int nr = r + m[0];
                int nc = c + m[1];
                if (nr >= 0 && nr < height && nc >= 0 && nc < width) {
                    if (img[nr][nc] == original) {
                        img[nr][nc] = newCol;
                        pixelQueue.push({nr, nc});
                    }
                }
            }
        }
    }

public:
    vector<vector<int>> applyFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        fillArea(image, sr, sc, newColor);
        return image;
    }
};