[백준 21938] 영상처리 (C++)

문제

---

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

세로 길이가 𝑁이고 가로 길이가 𝑀인 화면은 총 𝑁 × 𝑀개의 픽셀로 구성되어 있고 (𝑖,𝑗)에 있는 픽셀은 𝑅𝑖,𝑗 (Red), 𝐺𝑖,𝑗 (Green), 𝐵𝑖,𝑗 (Blue) 3가지 색상의 의미를 담고 있다. 각 색상은 0이상 255이하인 값으로 표현 가능하다.

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

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

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

입력

---

화면의 세로 𝑁, 가로 𝑀 값이 공백으로 구분되어 주어진다.

두 번째 줄부터 𝑁+1줄까지 𝑖번째 가로를 구성하고 있는 픽셀의 𝑅𝑖,𝑗, 𝐺𝑖,𝑗, 𝐵𝑖,𝑗의 값이 공백으로 구분되어 총 𝑀개 주어진다.

마지막 줄에는 경계값 𝑇가 주어진다.

출력

---

화면에 있는 물체의 개수를 출력하라. 만약 물체가 없으면 0을 출력하면 된다.

제한

---

•  1 ≤ 𝑁,𝑀 ≤ 1,000
•  0 ≤ 𝑅𝑖,𝑗,𝐺𝑖,𝑗,𝐵𝑖,𝑗 ≤ 255,  𝑅𝑖,𝑗,𝐺𝑖,𝑗,𝐵𝑖,𝑗 값은 정수
•  0 ≤ 𝑇 ≤ 255, 𝑇 값은 정수

문제 풀이

---

그래프 탐색 문제.

 

rgb 3 값을 평균 내 T보다 크거나 같다면 255, 아니라면 0으로 변환한 후 그래프 탐색하는 문제.

dfs, bfs 어느쪽을 사용해도 상관없다.

 

탐색할 때, 이미 방문하지 않은 칸이면서 N*M 배열을 벗어나지 않아야 하며, 물체의 개수를 확인해야 하므로 해당 칸의 값이 255이어야 한다.

 

아래는 dfs로 푼 코드.

현재 칸에서 상하좌우 중 방문 가능한 칸이 있다면 해당 칸을 바로 방문해야 하므로 움직일 다음 칸이 있는지 확인하는 boolean타입 isAdjacent를 넣고, 조건 검사 시 위 조건에 isAdjacent가 false인지를 추가한다. 4칸 중 가능한 칸이 있다면 스택에 넣고 isAdjacent를 true로 만들어 현재 칸에서 해당 칸 이외에는 방문하지 못하도록 한다.

#include <iostream>
#include <stack>
#include <utility>
using namespace std;
int N, M;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
int** arr;
bool** isVisited;
stack<pair<int, int>> dfsStack;

void dfs(int x, int y)
{
	dfsStack.push(pair(x, y));
	isVisited[x][y] = true;
	while (!dfsStack.empty())
	{
		pair<int, int> current = dfsStack.top();
		bool isAdjacent = false;
		for (int i = 0; i < 4; i++)
		{
			int nextX = dx[i] + current.first;
			int nextY = dy[i] + current.second;
			if (isAdjacent==false && nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && isVisited[nextX][nextY]==false && arr[nextX][nextY]==255)
			{
				isVisited[nextX][nextY] = true;
				dfsStack.push(pair(nextX, nextY));
				isAdjacent = true;
			}
		}
		if (isAdjacent == false)
		{
			dfsStack.pop();
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int T;
	int r, g, b;
	int answer = 0;
	cin >> N >> M;
	arr = new int*[N];
	isVisited = new bool*[N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[M];
		isVisited[i] = new bool[M];
		for (int j = 0; j < M; j++)
		{
			isVisited[i][j] = false;
			cin >> r >> g >> b;
			arr[i][j] = (r + g + b) / 3;
		}
	}
	cin >> T;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (arr[i][j] >= T)
			{
				arr[i][j] = 255;
			}
			else
			{
				arr[i][j] = 0;
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (arr[i][j] == 255 && isVisited[i][j] == false)
			{
				dfs(i, j);
				answer++;
			}
		}
	}
	cout << answer << "\n";
	return 0;
}