[코딩테스트] 백준 - 영상처리

영상처리 21938번 [17일차]

시간제한	메모리 제한
1초	512MB

문제

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

세로 길이가 N이고 가로 길이가 M인 화면은 총 N × M개의 픽셀로 구성되어 있고 (i,j)에 있는 픽셀은 Ri,j (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을 출력하면 된다.

 

 

제한

•  1≤N,M≤1,000
•  0≤Ri,j,Gi,j,Bi,j≤255, Ri,j,Gi,j,Bi,j 값은 정수
•  0≤T≤255, T 값은 정수

 

나의코드

package day17;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

// 영상처리 -  21938번
public class Solution2 {
    static boolean[][] visited;
    static int N;
    static int M;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};

    static int[][] arr;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        //입력
        // 첫번째줄
        // N*M
        // 방문 체크 배열
        // 3개씩 받아서 평균을 내서 arr에 넣어주기

        //기능
        // BFS를 이용해 너비우선탐색하기
        // 다음 탐색 - 마지막 경계값과 비교해 255일 경우 count+1 / 0 일경우


        //출력
        // count출력

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        arr = new int[M][N];
        visited = new boolean[M][N];

        //배열에 담기
        for (int i = 0; i < arr.length; i++) {
            String[] line = br.readLine().split(" ");
            int num = 0;
            for (int j = 0; j < arr[0].length; j++) {
                int sum = averageNum(num, line);
                num += 3;
                arr[i][j] = sum;
            }
        }


        int resultNum = Integer.parseInt(br.readLine());
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if(arr[i][j] >= resultNum){
                    arr[i][j] = 255;
                }else{
                    arr[i][j] = 0;
                }
            }
        }
        br.close();

        // 탐색
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && arr[i][j] == 255) {
                    bfs(i, j);
                    count++;
                }
            }
        }
        System.out.println(count);

    }

    static void bfs(int startX, int startY) {

        Deque<int[]> deque = new ArrayDeque<>();
        deque.offer(new int[]{startX, startY});
        visited[startX][startY] = true;


        while(!deque.isEmpty()){
            int[] now = deque.poll();
            int x = now[0];
            int y = now[1];


            visited[x][y] = true;

            for(int k = 0;k<4;k++) { //상하좌우 탐색
                int nowx = x + dx[k];
                int nowy = y + dy[k];

                if(nowx >=0 && nowy>=0 && nowx < arr.length && nowy < arr[0].length){
                    if (!visited[nowx][nowy] && arr[nowx][nowy] == 255) {
                        visited[nowx][nowy] = true;
                        deque.offer(new int[]{nowx, nowy});
                    }
                }
            }

        }

    }

    private static int averageNum(int num, String[] line){
        int sum = 0;
        for (int k = num; k < num + 3; k++) {
            sum += Integer.parseInt(line[k]);
        }
        sum /= 3;
        return sum;
    }
}

 

배열을 계산해서 받고 또 값을 비교해서 바꾸고,, 문제를 풀면서도 비효율적이라는 생각을 했었다

255라는 수를 따로 사용하는게 아니라 여부만 확인하기때문에 1(임의의수)로 바꿔줘도 무방할거 같다!