[백준/c++] BOJ 21938 - 영상처리

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

21938번: 영상처리

 

문제 설명

NxM 개의 픽셀로 구성된 화면이 있다. 각 픽셀은 Rij, Gij, Bij 3가지 색상의 의미를 담고 있다. 이는 0이상, 255이하의 값으로 표현이 가능하다. 모든 픽셀에서 세 가지 색상을 평균내어 경계값 T보다 크거나 같으면 픽셀의 값을 255로, 작으면 0으로 바꿔서 새로운 화면으로 저장한다. 값이 255인 픽셀은 물체로 인식하며, 상하좌우로 인접해 있다면 같은 물체로 인식한다. 물체가 총 몇 개 있는지 구한다.

N, M (1 <= N, M <= 1,000)

T (0 <= T <= 255)

해결

한 픽셀 당 R, G, B로 총 세 개의 입력이 들어온다. 세 개의 입력을 받은 후, 평균내어 배열에 저장한다.

이후에 경계값보다 크면 255로, 작으면 0으로 바꿔주는 작업을 진행하였다.

이후에 255면 물체로, 0이면 물체가 아닌 것으로 인식하여 bfs를 진행하면 쉽게 답을 구할 수 있다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;
int board[1001][1001];
int visited[1001][1001];
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0,1,-1 };
int ans = 0;

int range_over(int nx, int ny) {
    return nx < 0 || ny < 0 || nx >= n || ny >= m;
}

void bfs(int i, int j) {
    queue<pair<int, int>> q;
    q.push({ i ,j });
    visited[i][j] = 1;

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.x + dx[dir], ny = cur.y + dy[dir];
            if (range_over(nx, ny) || visited[nx][ny] || !board[nx][ny]) continue;
            visited[nx][ny] = 1;
            q.push({ nx, ny });
        }
    }
    ans++;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int a, b, c;
            cin >> a >> b >> c;
            board[i][j] = (a + b + c) / 3;
        }
    }
    int k;
    cin >> k;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] >= k) board[i][j] = 255;
            else board[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && board[i][j]) bfs(i, j);
        }
    }

    cout << ans;
}