[C/C++] 백준 - 21938번 : 영상처리

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

21938번: 영상처리

문제

간단하지만 귀찮은 영상처리 과제가 주어졌다. 과제의 명세는 다음과 같다.

세로 길이가 N$N$이고 가로 길이가 M$M$인 화면은 총 N$N$ × M$M$개의 픽셀로 구성되어 있고 (i,j)$(i, j)$에 있는 픽셀은 Ri,j$R_{i,j}$ (Red), Gi,j$G_{i,j}$ (Green), Bi,j$B_{i,j}$ (Blue) 3가지 색상의 의미를 담고 있다. 각 색상은 0이상 255이하인 값으로 표현 가능하다.

모든 픽셀에서 세 가지 색상을 평균내어 경계값 T$T$보다 크거나 같으면 픽셀의 값을 255로, 작으면 0으로 바꿔서 새로운 화면으로 저장한다.

새로 만들어진 화면에서 값이 255인 픽셀은 물체로 인식한다. 값이 255인 픽셀들이 상하좌우로 인접해있다면 이 픽셀들은 같은 물체로 인식된다.

화면에서 물체가 총 몇 개 있는지 구하는 프로그램을 작성하시오.

---

이 문제 또한 BFS 개념 문제인데 BFS를 적용하기 전 픽셀의 값을 Red, Green, Blue 값에 따라 다시 255 또는 0으로 저장해주어야한다.

그리고 255인 픽셀에서만 BFS를 적용하여 상하좌우로 인접해있는 픽셀들을 하나의 물체로 인식하여 총 몇 개의 물체가 존재하는지 알아내면 되는 문제이다.

 

쉬운 문제이니 코드로 충분히 이해할 수 있을 듯 하다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

typedef struct color{
    int red;
    int green;
    int blue;
}Color;

int N, M, T;
int cache[1000 + 1][1000 + 1];
Color board[1000 + 1][1000 + 1];
bool visited[1000 + 1][1000 + 1];
const int dy[] = {1, -1, 0, 0};
const int dx[] = {0, 0, 1, -1};

void input(){
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            cin >> board[i][j].red >> board[i][j].green >> board[i][j].blue;
        }
    }
    cin >> T;
}

void saveValue(){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            int total = 0;
            total += board[i][j].red + board[i][j].green + board[i][j].blue;
            if(T <=total / 3) {
                cache[i][j] = 255;
            }
            else{
                cache[i][j] = 0;
            }
        }
    }
}

bool isValid(int y, int x){
    return (1 <= y && y <= N && 1 <= x && 1 <= M);
}

void spread(int y, int x){
    queue<pair<int, int>> q;
    q.push({y, x});

    while(!q.empty()){
        int curY = q.front().first;
        int curX = q.front().second;
        q.pop();

        for(int i=0;i<4;i++){
            int ny = curY + dy[i];
            int nx = curX + dx[i];

            if(!isValid(ny, nx) || visited[ny][nx] || cache[ny][nx] != 255) continue;
            q.push({ny, nx});
            visited[ny][nx] = true;
        }
    }
}

int countX(){
    int answer = 0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(!visited[i][j] && cache[i][j] == 255){
                visited[i][j] = true;
                answer++;
                spread(i, j);
            }
        }
    }
    return answer;
}

int solution(){
    saveValue();
    return countX();
}

int main(void){
    fastio;
    input();
    cout << solution() << endl;

    return 0;
}