[백준] S2 21938번 영상처리 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

21938번: 영상처리

[문제] 

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

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

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

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

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

[입력]

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

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

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

[출력]

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

 

---

[풀이]

1. 값들을 입력받아준다.

2. r, g, b를 입력받아 해당 값들의 평균을 map에 채워준다.

3. t를 입력받고 map을 재탐색하며 t 이상의 값은 255, 아니라면 0으로 갱신해준다.

4. 이후 dfs탐색을 통해 영역의 개수를 구한다.

5. 결과를 출력한다.

[접근]

1. 입력으로 주어진 rgb들의 평균으로 map을 채워 t의 조건에 맞춰 맵을 재구성해준다.

2. 이후, dfs 탐색을 하면 되겠다고 생각하였다.

[코드]

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	static int n, m, t;
	static int map[][];
	static boolean visited[][];
	static int cnt;
	
	static int dr[] = {-1, 1, 0, 0};
	static int dc[] = {0, 0, -1, 1};

	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];
		visited = new boolean[n][m];
		
		// 채우기
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < m; j++) {
				// 평균을 내기 위한 r, g, b
				int r = Integer.parseInt(st.nextToken());
				int g = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				// 위에서 받은 r, g, b의 평균값으로 map에 채움
				map[i][j] = (r + g + b) / 3;
			}
		}
		
		// 입력받기
		t = Integer.parseInt(br.readLine());
		
		// t 이상일 경우 255 아니면 0으로 채워주기
		for (int i = 0; i < n; i++) {
			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++) {
			for (int j = 0; j < m; j++) {
				// 255거나 방문하지 않은곳이라면
				if (map[i][j] == 255 && !visited[i][j]) {
					// dfs 탐색
					dfs(i, j);
					// 구역 갯수 증가
					cnt++;
				}
			}
		}
		
		System.out.println(cnt);
	}
	
	private static void dfs(int x, int y) {
		// 해당 지역 방문 체크
		visited[x][y] = true;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dr[i];
			int ny = y + dc[i];
			
			// 범위를 벗어나면 continue
			if (nx < 0 || ny < 0 || nx >= n || ny >= m)
				continue;
			
			// 탐색가능한 곳이고 방문하지 않은 곳이라면
			if (map[nx][ny] != 0 && !visited[nx][ny])
				// 추가 탐색
				dfs(nx, ny);
		}
	}
}