[C++]백준 30106번 현이의 로봇 청소기

📌문제 링크

---

https://www.acmicpc.net/problem/30106

📌문제 설명

---

전형적인 flood fill 문제이다. dfs, bfs 둘다 가능하다. 탐색하며 영역 간 높이 차가 K 이하이면 같은 영역으로 색칠한다. 모든 지역 탐색 후 영역의 개수를 출력한다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
bool visited[501][501];
int N, M, K, answer, mp[501][501];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};


void input(){
    cin >> N >> M >> K;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> mp[i][j];
        }
    }
}

void bfs(int x, int y){
    queue<pair<int, int>> q;
    visited[x][y] = true;
    q.push({x, y});
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny]){
                continue;
            }
            if(abs(mp[x][y] - mp[nx][ny]) > K){
                continue;
            }
            visited[nx][ny] = true;
            q.push({nx, ny});
        }
    }
}

void solve(){
    input();
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(!visited[i][j]){
                bfs(i, j);
                answer++;
            }
        }
    }
    cout << answer;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}