[Python] BOJ 백준 21938 영상처리

문제

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

세로 길이가 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인 픽셀들이 상하좌우로 인접해있다면 이 픽셀들은 같은 물체로 인식된다.

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

풀이

너비 탐색을 이용해서 풀었다. 초기에 문제를 잘못 이해해서 삽질을 좀 했던 문제.

case를 음수로 만들어놓고 주변으로 퍼져나가면서 -1, -2, ... 점점 내려가서 결국 minimum값을 양수로 만들어주면 답이 된다.

파싱하는 부분이 귀찮았는데, 다른 방법을 강구해보는 것도 좋을 것 같다. 

import sys
from collections import deque, Counter

si = sys.stdin.readline
def MIIS(): return map(int, si().split())


n, m = MIIS()
screen = [list(MIIS()) for _ in range(n)]
t = int(si())

graph = [[] * m for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False] * m for _ in range(n)]

for i in range(n):
    line = screen[i]
    col = 0
    for j in range(0, (3 * m), 3):
        avg = sum(line[j:j + 3])
        if avg >= (t * 3):
            avg = 255
        else:
            avg = 0
        graph[i].append(avg)
        col += 1


def bfs(start, num):
    q = deque()
    q.append(start)
    while q:
        x, y = q.popleft()
        graph[x][y] = num
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 255 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))


case = -1
for i in range(n):
    for j in range(m):
        if graph[i][j] == 255:
            bfs((i, j), case)
            case -= 1


answer = min([min(arg) for arg in graph])
print(answer * - 1)