방과후
ALGORITHM NOTE약 2분

BOJ 33065 - Observing Objects

RGBRGB

#algorithm#boj#silver#graph-theory#graph-traversal#grid
아카이브로 돌아가기

문제 링크

문제

In image processing fundamentals, determining the region where an object is located is crucial.

You are given a screen of size N×MN\times M, consisting of NMNM pixels. Each pixel at position (i,j)(i,j) has a specific RGB value represented by three integers: RijR_{ij}​ (Red), GijG_{ij}​ (Green), and BijB_{ij}​ (Blue). Each color component is an integer in the [0,255][0,255] range.

The task is to identify the number of distinct objects on the screen. Two pixels are considered part of the same object if their RGB values are identical and connected in one of the 88 possible directions: up, down, left, right, and the 44 diagonals.

An object is defined as a group of connected pixels that meet the above criteria. Write a program to determine the number of distinct objects on the screen.

입력

The first line contains two space-separated integers, NN and MM, denoting the size of the image. (1≤N,M≤1 0001 \le N,M \le 1\,000)

The following NN lines contain 3NM3NM integers, where each line has 3M3M space-separated integers, denoting the RGB value of each pixel. Here, the 3j3j-th, the (3j+1)(3j+1)-th, and the (3j+2)(3j+2)-th integer of the ii-th row denotes RijR_{ij}​, GijG_{ij}​, and BijB_{ij}​, respectively. (0≤Rij,Gij,Bij≤2550 \le R_{ij},G_{ij},B_{ij} \le 255)

출력

Output the total number of distinct objects in the screen.

풀이

같은 RGB 값을 가진 픽셀들이 8방향으로 이어져 있으면 하나의 물체다. 따라서 아직 방문하지 않은 픽셀에서 BFS를 시작하고, 현재 픽셀과 RGB가 완전히 같은 이웃만 큐에 넣어 끝까지 퍼뜨리면 물체 하나를 전부 찾을 수 있다.

코드는 Color 클래스로 RGB를 묶고 isSame으로 색 일치 여부를 검사한다. 전체 격자를 훑으면서 BFS를 몇 번 시작했는지를 세면, 그 수가 곧 화면 속 물체 개수다.

코드

java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
 
    private static final StringBuilder sb = new StringBuilder();
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static class Color {
        int R, G, B;
 
        Color (int R, int G, int B) {
            this.R = R;
            this.G = G;
            this.B = B;
        }
 
        public boolean isSame(Color color) {
            if (color == null) return false;
            return this.R == color.R && this.G == color.G && this.B == color.B;
        }
    }
 
    public static class Node {
        int X, Y;
 
        Node (int X, int Y) {
            this.X = X;
            this.Y = Y;
        }
    }
 
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        Color[][] map = new Color[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
 
            for (int j = 0; j < M; j++) {
                int R = Integer.parseInt(st.nextToken());
                int G = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());
 
                map[i][j] = new Color(R, G, B);
            }
        }
 
        solve(N, M, map);
        System.out.println(sb);
        br.close();
    }
 
    public static void solve(int N, int M, Color[][] map) throws IOException {
        boolean[][] visited = new boolean[N][M];
        int count = 0;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j]) {
                    bfs(i, j, N, M, map, visited);
                    count++;
                }
            }
        }
 
        sb.append(count);
    }
 
    public static void bfs(int x, int y, int N, int M, Color[][] map, boolean[][] visited) {
        Deque<Node> deq = new ArrayDeque<>();
        deq.add(new Node(x, y));
        visited[x][y] = true;
 
        int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
        int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
 
        while (!deq.isEmpty()) {
            Node now = deq.poll();
 
            for (int i = 0; i < 8; i++) {
                int nx = now.X + dx[i];
                int ny = now.Y + dy[i];
 
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (!visited[nx][ny] && map[now.X][now.Y].isSame(map[nx][ny])) {
                    visited[nx][ny] = true;
                    deq.push(new Node(nx, ny));
                }
            }
 
        }
    }
}

복잡도

  • 시간 복잡도: 화면의 모든 픽셀을 BFS로 한 번씩 확인하므로 O(NM)O(NM)이다.
  • 공간 복잡도: 픽셀 배열과 방문 배열을 저장하므로 O(NM)O(NM)이다.

마무리

같은 RGB 값을 가진 픽셀들이 8방향으로 이어져 있으면 하나의 물체다.