[Java] Boj 1895: 필터

문제

숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10)

이미지 I는 크기가 R × C인 2차원 픽셀이다. (3 ≤ R ≤ 40, 3 ≤ C ≤ 40) 각 픽셀은 어두운 정도 V를 나타낸다. (0 ≤ V ≤ 255)

중앙 필터는 이미지에 있는 노이즈를 제거하는 필터이다. 필터의 크기는 3 × 3이고, 이미지의 중앙값을 찾으면서 잡음을 제거한다.

예를 들어, 아래와 같은 6 × 5 이미지가 있다.

필터링된 이미지의 크기는 4 × 3이고, 아래와 같다.

가장 왼쪽 윗 행에 필터를 두고, 오른쪽으로 움직이면서 중앙값을 찾는다. 한 행을 모두 이동했으면, 다음 행으로 이동해 다시 중앙값을 찾는다. 아래와 같은 순서를 가진다.

위의 그림에서 각각의 중앙값은 36, 36, 21이 된다. 이 값은 필터링된 이미지 J의 첫 행과 같다. 

이미지 I가 주어졌을 때, 필터링 된 이미지 J를 구하고, 값이 T보다 크거나 같은 픽셀의 수를 구하는 프로그램을 작성하시오.

예를 들어, T = 40일 때, 위의 예에서 정답은 7이다. 

 

입력

첫째 줄에 이미지의 크기 R과 C가 주어진다. 그 다음 R개의 각 줄에는 C개의 픽셀 값이 주어진다. 마지막 줄에는 T값이 주어진다.

출력

첫째 줄에 필터링 된 이미지 J의 각 픽셀 값 중에서 T보다 크거나 같은 것의 개수를 출력한다.

---

풀이

입력받는 2차원 배열에 대해 3 * 3 필터로 중앙값을 찾고, 그 중앙값이 T보다 크다면 count를 증가시켜주면 되는 단순 구현 문제이다.

여담으로 문제가 인공지능의 노이즈 제거와 관련이 있는데, 커널의 중앙값을 택해 영상을 필터링하는 방법으로 이 방법을 중간값 필터링이라 한다.

인공지능 강의가 어려워서 따라가기 정말 힘들었는데 오랜만에 필터링을 또 보니까 뭔가 반가운..?

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        PriorityQueue<Integer> pq;
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] arr = new int [n][m];
        int cnt = 0;
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j=0; j<m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int t = Integer.parseInt(bf.readLine());
        for (int i=0; i<n-2; i++) {
            for (int j=0; j<m-2; j++) {
                pq = new PriorityQueue<>();
                for (int x=i; x<=i+2; x++) {
                    for (int y=j; y<=j+2; y++) {
                        pq.add(arr[x][y]);
                    }
                }
                for (int x = 0; x < 4; x++) {
                    pq.poll();
                }
                if (pq.poll() >= t)
                    cnt++;
            }
        }
        System.out.println(cnt);
    }
}