문제

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

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

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

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

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

import sys

input = lambda: sys.stdin.readline().strip()

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m = map(int, input().split())
graph = []
for i in range(n):
  pixel = list(map(int, input().split()))
  graph.append([])
  for j in range(0, 3 * m, +3):
    num = (pixel[j] + pixel[j + 1] + pixel[j + 2]) // 3
    graph[i].append(num)
t = int(input())

visited = [[False] * m for _ in range(n)]


def bfs(x, y, t):
  queue = deque()
  queue.append((x, y, t))
  while queue:
    x, y, t = queue.popleft()
    visited[y][x] = True
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= m or ny >= n:
        continue
      if graph[ny][nx] >= t and visited[ny][nx] == False:
        visited[ny][nx] = True
        queue.append((nx, ny, t))


count = 0
for i in range(n):
  for j in range(m):
    if graph[i][j] >= t and visited[i][j] == False:
      bfs(j, i, t)
      count += 1

print(count)

백준 21938 영상처리