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

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

풀이

이 문제는 영상 처리와 관련된 문제로, 주어진 이미지에서 각 픽셀의 색상(RGB)을 평균내어, 경계값 T를 기준으로 이진화(Thresholding) 처리를 한 후, 이진화된 이미지에서 물체(255로 인식되는 영역)의 개수를 찾는 문제입니다.

문제 해결 방법

1. 입력 처리:
   • 화면 크기 N x M을 입력받고, 각 픽셀의 RGB 값을 읽어옵니다.
   • RGB 값의 평균을 계산하여 map[][] 배열에 저장합니다.
2. 이진화(Thresholding):
   • 주어진 경계값 T를 기준으로, 평균값이 T 이상이면 255(물체), 그렇지 않으면 0(배경)으로 설정합니다.
3. DFS(깊이 우선 탐색):
   • 255로 연결된 영역을 찾기 위해 DFS를 사용하여 상하좌우로 인접한 255 픽셀들을 하나의 물체로 간주합니다.
   • 방문한 픽셀은 visited[][] 배열에 기록하여 중복 탐색을 방지합니다.
4. 결과 출력:
   • 각 물체가 발견될 때마다 물체의 개수를 증가시키고, 최종적으로 총 물체의 개수를 출력합니다.

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

public class Main {
    static int n, m, t;
    static int map[][];
    static boolean visited[][];
    static int cnt;

    // 방향 벡터 (상, 우, 하, 좌)
    static int dy[] = {-1, 0, 1, 0};
    static int dx[] = {0, 1, 0, -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];

        // RGB 입력을 받아 평균값을 계산하여 map에 저장
        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());

                // RGB 평균값을 map에 저장
                map[i][j] = (r + g + b) / 3;
            }
        }

        // 경계값 T 입력
        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;    // 배경
                }
            }
        }

        // 물체의 개수를 세기 위한 DFS 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 물체(255)이고, 방문하지 않은 경우
                if (map[i][j] == 255 && !visited[i][j]) {
                    dfs(i, j);  // 물체 탐색
                    cnt++;      // 물체 개수 증가
                }
            }
        }

        // 결과 출력: 총 물체의 개수
        System.out.println(cnt);
    }

    // DFS로 물체 탐색 (연결된 255인 영역 탐색)
    private static void dfs(int y, int x) {
        // 방문 처리
        visited[y][x] = true;

        // 4방향 탐색 (상, 우, 하, 좌)
        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) continue;

            // 물체(255)이고, 아직 방문하지 않은 경우 DFS 호출
            if (map[ny][nx] == 255 && !visited[ny][nx]) {
                dfs(ny, nx);
            }
        }
    }
}

시간 복잡도 분석

1. 입력 처리:
   • n x m 크기의 배열에 대해 모든 픽셀에 대해 RGB 값을 평균내는 작업은 O(n * m)입니다.
2. 이진화 처리:
   • 경계값 T와 비교하여 배열 값을 255 또는 0으로 변경하는 작업 역시 O(n * m)입니다.
3. DFS 탐색:
   • 모든 픽셀을 탐색하고, 255로 연결된 영역을 찾는 DFS는 최악의 경우 모든 픽셀을 한 번씩 탐색할 수 있습니다. 즉, DFS 탐색의 시간 복잡도는 O(n * m)입니다.
4. 최종 시간 복잡도:
   • 입력 처리, 이진화, DFS 탐색을 각각 한 번씩 수행하므로 전체 시간 복잡도는 O(n * m)입니다.

공간 복잡도 분석

1. 입력 배열 map[][]:
   • n x m 크기의 배열을 사용하므로 O(n * m)의 공간이 필요합니다.
2. 방문 배열 visited[][]:
   • 각 픽셀의 방문 여부를 기록하는 visited 배열 역시 O(n * m)의 공간을 차지합니다.
3. 재귀 호출 스택:
   • DFS는 재귀 호출을 사용하므로, 최악의 경우 스택 깊이는 O(n * m)일 수 있습니다. 재귀 호출이 너무 깊어질 경우 스택 오버플로우를 방지하기 위해 반복 구조로 DFS를 바꾸는 것이 좋을 수 있습니다.

알고리즘 및 자료구조

1. 알고리즘:
   • 이진화: 주어진 RGB 값들을 평균내고 경계값 T를 기준으로 255와 0으로 변환하는 작업.
   • DFS 탐색: DFS를 이용해 255로 연결된 영역을 하나의 물체로 인식하여 물체의 개수를 셉니다.
2. 자료구조:
   • 2차원 배열 map[][]: 각 픽셀의 평균값 및 이진화 값을 저장하는 배열.
   • 2차원 배열 visited[][]: 각 픽셀의 방문 여부를 기록하는 배열.

개선 및 최적화

1. 메모리 절약:
   • visited[][] 배열을 사용하지 않고, map[][] 배열의 값을 255에서 -1로 변환하여 이미 탐색한 물체의 픽셀을 표시하는 방법으로 메모리 사용을 줄일 수 있습니다.
2. 스택 오버플로우 방지:
   • DFS 대신 반복 구조의 DFS(명시적 스택 사용)를 적용하면 스택 오버플로우를 방지할 수 있습니다.