Baekjoon 21938 영상처리 JAVA

21938번: 영상처리

문제

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

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

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

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

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

 

조건

[입력]

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

두 번째 줄부터 N+1줄까지 i번째 가로를 구성하고 있는 픽셀의 Ri, j, Gi, j, Bi, j의 값이 공백으로 구분되어 총 M개 주어진다.

마지막 줄에는 경곗값 T가 주어진다.

 

[출력]

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

 

풀이

해당 문제는 픽셀 값을 통해 0 또는 255로 변환하여 같은 물체가 몇 개인지 구하는 문제다.

문제에서 주어진대로 구현을 하면 되고 bfs나 dfs를 이용하면 해결 가능하다. 로직은 아래와 같은 방식으로 구현하였다.

1. 입력 처리를 하면서 평균값을 저장한다.

2. 입력 처리가 끝나면 배열을 탐색하면서 255 or 0으로 갱신한다.

3. dfs를 돌면서 체크한다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, M,T,ans, map[][], dy[] = {-1,1,0,0}, dx[] = {0,0,-1,1};
	static boolean[][] visit;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) { // 입력처리하면서 평균값으로 저장한다.
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int sum = Integer.parseInt(st.nextToken())+ Integer.parseInt(st.nextToken())+ Integer.parseInt(st.nextToken());
				map[i][j] = sum / 3;
			}
		}
		T = Integer.parseInt(br.readLine());
		for (int i = 0; i < N; i++) { // T값 이상인 값들은 255로 아닌값은 0으로 변경한다
			for (int j = 0; j < M; j++) {
				if(map[i][j] >= T)
					map[i][j] = 255;
				else
					map[i][j] = 0;
			}
		}
		for (int i = 0; i < N; i++) { // dfs돌면서 체크한다
			for (int j = 0; j < M; j++) {
				if(map[i][j] == 255 && !visit[i][j]) {
					dfs(i,j);
					ans++;
				}
			}
		}
		System.out.println(ans);
	}
	private static void dfs(int y, int x) {
		visit[y][x] = true;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || nx < 0 || ny >= N || nx >= M || visit[ny][nx] || map[ny][nx] == 0)
				continue; // 배열 범위 벗어나거나 이미 방문했거나 0이면 다음반복 진행
			dfs(ny,nx);
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드