[ BOJ ][JAVA][21938] 영상처리

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

21938번: 영상처리

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	312	118	97	38.189%

문제

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

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

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

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

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

입력

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

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

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

출력

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

제한

•  1≤N,M≤1,000$1 \le N, M \le 1,000$ 
•  0≤Ri,j,Gi,j,Bi,j≤255$0 \le R_{i,j}, G_{i,j}, B_{i,j} \le 255$, Ri,j,Gi,j,Bi,j$R_{i,j}, G_{i,j}, B_{i,j}$ 값은 정수
•  0≤T≤255$0 \le T \le 255$, T$T$ 값은 정수

예제 입력 1

3 3
255 255 255 100 100 100 255 255 255
100 100 100 255 255 255 100 100 100
255 255 255 100 100 100 255 255 255
101

예제 출력 1

5

예제 입력 2

2 2
124 150 123 100 100 100
103 103 103 183 5 3
255

예제 출력 2

0

접근

단순히 주어진 대로 구현하는 문제였고

시간을 비교하기 위해, DFS와 BFS 모두 사용해보았지만 큰 차이는 없었다.

코드

/**
 * BOJ 21938 영상처리 Silver2
 * dfs / bfs :: 시간은 어느 걸 쓰나 비슷하게 나온다.
 */
import java.io.*;
import java.util.*;

public class p21938 {
    static class Point {
        int r, c;
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    static int n, m, t;
    static double[][] screen;
    static boolean[][] visited;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        init();
        System.out.println(solution());
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        screen = new double[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++) {
                double rgb = Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());
                rgb /= 3;
                screen[i][j] = rgb;
            }
        }

        t = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (screen[i][j] < t) screen[i][j] = 0;
            }
        }
    }

    static int solution() {
        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (screen[i][j] > 0 && visited[i][j] == false) {
                    dfs(i, j);
                    answer++;
                }
            }
        }
        return answer;
    }

    static void dfs(int r, int c) {
        visited[r][c] = true;

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (OOB(nr, nc)) continue;
            if (visited[nr][nc]) continue;
            if (screen[nr][nc] <= 0) continue;

            dfs(nr, nc);
        }
    }

    static void bfs(int r, int c) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r, c));
        visited[r][c] = true;

        while (!q.isEmpty()) {
            Point cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                if (OOB(nr, nc)) continue;
                if (visited[nr][nc]) continue;
                if (screen[nr][nc] <= 0) continue;

                q.add(new Point(nr, nc));
                visited[nr][nc] = true;
            }
        }
    }

    static boolean OOB(int r, int c) {
        return r < 0 || c < 0 || r >= n || c >= m;
    }
}