[백준/21938] 영상처리 - 파이썬(Python)

문제

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

세로 길이가 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 값은 정수
•  0≤T≤255 값은 정수

---

예제 입력 1

3 3
255 255 255 100 100 100 255 255 255
100 100 100 255 255 255 100 100 100
255 255 255 100 100 100 255 255 255
101

예제 출력 1

5

예제 입력 2

2 2
124 150 123 100 100 100
103 103 103 183 5 3
255

예제 출력 2

0

 

21938번: 영상처리

 

 

문제 풀이

문제의 내용처럼, 입력을 다 받은 후 경곗값 기준에 따라서 값을 저장해줬는데, 어차피 T(경곗값)이 정수여서 나눠주지 않고 값을 저장 후 T*3값과 비교해도 됐을 것 같다.

이후 BFS나 DFS로 문제를 풀면 된다.

from collections import deque
input = __import__('sys').stdin.readline
MIIS = lambda: map(int, input().split())

# 입력
N, M = MIIS()
pixels = []
screen = [[] for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
for _ in range(N):
	pixels.append(list(MIIS()))
T = int(input())

# 화면 값 계산
for i in range(N):
	for j in range(0,M*3,3):
		if sum(pixels[i][j:j+3])/3 < T:
			screen[i].append(0)
		else :
			screen[i].append(255)

# 물체 계산
que = deque()
# 상(-1, 0), 하(1, 0), 좌(0, -1), 우(0, 1)
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]


def bfs(r, c):
	que.append((r,c))
	visited[r][c] = True
	
	while que:
		x, y = que.popleft()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if 0 <= nx < N and 0 <= ny < M:
				if not visited[nx][ny] and screen[nx][ny] == 255:
					visited[nx][ny] = True
					que.append((nx,ny))
cnt = 0
for x in range(N):
	for y in range(M):
		if screen[x][y] == 255  and not visited[x][y]:
			bfs(x,y)
			cnt += 1

print(cnt)