(C++) - LeetCode (easy) 733. Flood Fill

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

Flood Fill - LeetCode

graph 탐색 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

4방향을 확인할 일차원 배열 dr, dc, image의 높이 height, 너비 width, {sr, sc} 좌표의 원래 색 originColor, image크기의 방문 여부를 확인할 2차원 vector check를 선언해줍니다.

📔 풀이과정

bfs로 {sr, sc} 부터 시작해 4방향을 검사하며 확인한 좌표가 방문한적 없고 originColor라면 "인접"해 있으므로 방문해주면서 해당 좌표의 색을 color로 칠해준 뒤 queue에 넣어줍니다.

📔 정답 출력 | 반환

새롭게 칠해진 image를 반환합니다.

---

📕 Code

📔 C++

using pii = pair<int,int>;
class Solution {
    int dr[4] = {0,0,1,-1};
    int dc[4] = {1,-1,0,0};
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int height = image.size();
        int width = image[0].size();
        int originColor = image[sr][sc];
        vector<vector<int>> check(height,vector <int>(width,0));
        check[sr][sc] = 1;
        image[sr][sc] = color;
        queue <pii> q;
        q.push({sr,sc});
        
        while(q.size()) {
            int r = q.front().first;
            int c = q.front().second;
            q.pop();
            for(int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if(0 > nr || nr >= height || 0 > nc || nc >= width) continue;
                if(image[nr][nc] != originColor || check[nr][nc]) continue;
                check[nr][nc] = 1;
                image[nr][nc] = color;
                q.push({nr,nc});
            }
        }
        return image;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.