[백준] 영상처리 (Python)

규갓 God Gyu·2024년 8월 5일
백준

백준

목록 보기
44/96

문제

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

세로 길이가 NN이고 가로 길이가 MM인 화면은 총 NN × MM개의 픽셀로 구성되어 있고 (i,j)(i, j)에 있는 픽셀은 Ri,jR_{i,j} (Red), Gi,jG_{i,j} (Green), Bi,jB_{i,j} (Blue) 3가지 색상의 의미를 담고 있다. 각 색상은 0이상 255이하인 값으로 표현 가능하다.

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

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

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

입력

화면의 세로
NN, 가로
MM 값이 공백으로 구분되어 주어진다.

두 번째 줄부터 N+1N + 1줄까지 ii번째 가로를 구성하고 있는 픽셀의 Ri,jR_{i,j}, Gi,jG_{i,j}, Bi,jB_{i,j}의 값이 공백으로 구분되어 총 MM개 주어진다.

마지막 줄에는 경계값 TT가 주어진다.

출력

화면에 있는 물체의 개수를 출력하라. 만약 물체가 없으면 0을 출력하면 된다.

제한

  • 1≤N,M≤1,0001 \le N, M \le 1,000 

  • 0≤Ri,j,Gi,j,Bi,j≤2550 \le R_{i,j}, G_{i,j}, B_{i,j} \le 255,

  • Ri,j,Gi,j,Bi,jR_{i,j}, G_{i,j}, B_{i,j} 값은 정수

  • 0≤T≤2550 \le T \le 255, TT 값은 정수

예제 입력 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

최종 코드

# 영상처리
# 세로 N 가로 M (NxM)
# (i,j)에 있는 픽셀은 R,G,B 세가지 색상(0~255)
# 모든 픽셀에서 세 가지 색상 평균 내서 경계값 T보다 크거나 같으면 255, 작으면 0
# 255- 물체, 상하좌후 인접 시 - 같은 물체
# 물체가 총 몇개인지??
# ===========================
# 세로 N, 가로 M
# N+1줄까지 i번째 가로 구성하는 R,G,B의 값이 공백으로 구분 총 M개
# 마지막 줄 경계값 T
# 물체의 개수 출력, 없으면 0
#=============================
# import sys
# from collections import deque

# # N, M
# N, M = map(int, sys.stdin.readline().split())
# #(x,y)로 접근할 세팅해줄 리스트안의 리스트로 선언
# display = [sys.stdin.readline().strip().split() for _ in range(N)]
# # 물체연결 체크(길이가 3xM만큼인 것 같아서..?)
# object = [[False]*(3*N) for _ in range(N)]
# # 현재 위치 담을
# queue = deque()
# # 상하좌우
# directions = [(-1,0), (1,0), (0,-1), (0,1)]
# while queue:
# ==============================
# 있는 그대로 255가 3개까지 이어져있으면 물체1개 이렇게 구현하려했으니, 255가 6개일때, 가로, 세로 이어진 물체일때를 체크하기까지 떠오르지 않음
# =============================
# 3가지 연속된 수의 평균이 T보다 크면 255로 , 작으면 0으로 변환 ☆☆

import sys
from collections import deque

input = sys.stdin.read
data = input().split()
  
# 화면 세로, 가로
N = int(data[0])
M = int(data[1])
  
# 경계값
T = int(data[-1])
  
# 픽셀 초기 값
pixels = []
# index는 2부터 시작
index = 2
# N만큼 반복하며 Mx3(R,G,B)를 담아줄 반복문
for _ in range(N):
  # 한 줄
  row = [int(data[index + j]) for j in range(M*3)]
  # pixels에 담아주기
  pixels.append(row)
  # 그 다음 줄을 읽어오기 위한 index 설정
  index += M * 3
  
# 새롭게 이진화시킨 화면 배열(255 or 0) 초기 값
binary_image = [[0]*M for _ in range(N)]

# ??
visited = [[False]*M for _ in range(N)]
# N만큼 반복하기(줄)
for i in range(N):
  # M만큼 반복하기(칸) - 3개의 합산평균이기에 3*M해줄 필요 없음
  for j in range(M):
    R = pixels[i][j*3]
    G = pixels[i][j*3+1]
    B = pixels[i][j*3+2]
    # 3숫자의 평균 값
    avarage = (R+G+B) / 3
    # 이번에 처음본 삼항 연산자!!!!!!!!!!!!!! ☆☆☆☆☆
    binary_image[i][j] = 255 if avarage >= T else 0
      
  # 물체 탐색 BFS 함수
def bfs(start_x, start_y):
  # 초기 값 큐에 추가
  # []안의 튜플로 넣어야 하나의 요소로 들어갈 수 있음
  queue = deque([(start_x,start_y)])
  # 해당 위치는 True로 변환
  visited[start_x][start_y] = True
  # queue에 값이 있는 동안 계속 반복
  while queue:
    # 최초 값 뽑아내기(왼쪽에서)
    x, y = queue.popleft()
    # 상하좌우 값
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    
    for dx, dy in directions:
      # 기존 값에 새로운 위치 반영한 결과
      nx, ny = x + dx, y+ dy
      # N,M범위 안에서 한번 체크한 곳 제외, 255 숫자가 존재할시 
      if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and binary_image[nx][ny] == 255:
        # binary_image boolean 변화
        visited[nx][ny] = True
        # 초기값 변경
        queue.append((nx,ny))
        
# 물체 개수
object_count = 0

for i in range(N):
  for j in range(M):
    if binary_image[i][j] == 255 and not visited[i][j]:
      bfs(i, j)
      object_count += 1
      
print(object_count)
# 영상처리
# 세로 N 가로 M (NxM)
# (i,j)에 있는 픽셀은 R,G,B 세가지 색상(0~255)
# 모든 픽셀에서 세 가지 색상 평균 내서 경계값 T보다 크거나 같으면 255, 작으면 0
# 255- 물체, 상하좌후 인접 시 - 같은 물체
# 물체가 총 몇개인지??
# ===========================
# 세로 N, 가로 M
# N+1줄까지 i번째 가로 구성하는 R,G,B의 값이 공백으로 구분 총 M개
# 마지막 줄 경계값 T
# 물체의 개수 출력, 없으면 0
#=============================
# import sys
# from collections import deque

# # N, M
# N, M = map(int, sys.stdin.readline().split())
# #(x,y)로 접근할 세팅해줄 리스트안의 리스트로 선언
# display = [sys.stdin.readline().strip().split() for _ in range(N)]
# # 물체연결 체크(길이가 3xM만큼인 것 같아서..?)
# object = [[False]*(3*N) for _ in range(N)]
# # 현재 위치 담을
# queue = deque()
# # 상하좌우
# directions = [(-1,0), (1,0), (0,-1), (0,1)]
# while queue:
# ==============================
# 있는 그대로 255가 3개까지 이어져있으면 물체1개 이렇게 구현하려했으니, 255가 6개일때, 가로, 세로 이어진 물체일때를 체크하기까지 떠오르지 않음
# =============================
# 3가지 연속된 수의 평균이 T보다 크면 255로 , 작으면 0으로 변환 ☆☆

여기서 어차피 입력에 255가 3개가 있으니, 그게 3개가 이어져 있는게 물체 1개 근데 그게 붙어져있으면 큰 물체 이런식으로 접근했었는데, 그걸 구분짓기가 어려울 것 같았고, RGB의 평균값을 T와 비교하라는걸 입력에 보면 어차피 255잖아? 라고 접근했지만, 자세히 살펴보면 두번째 예제는 값이 다르게 나올 수 도 있어서 255 혹은 0처리를 해줬어야 했다.

import sys
from collections import deque

일단 BFS를 활용해서 풀 문제여서 입력 문법 sys와 deque사용 예정(양쪽 제거 삽입)

input = sys.stdin.read
data = input().split()

일단 모든 값 data에 담아주기

# 화면 세로, 가로
N = int(data[0])
M = int(data[1])

# 경계값
T = int(data[-1])

바로 뽑아낼 수 있는 N,M,T는 int처리해서 받아오기

# 픽셀 초기 값
pixels = []
# index는 2부터 시작
index = 2
# N만큼 반복하며 Mx3(R,G,B)를 담아줄 반복문
for _ in range(N):
  # 한 줄
  row = [int(data[index + j]) for j in range(M*3)]
  # pixels에 담아주기
  pixels.append(row)
  # 그 다음 줄을 읽어오기 위한 index 설정
  index += M * 3

그래픽 관련 내용은 pixels에 넣어줄 예정이고,
앞에 0,1인덱스는 N,M뽑아내는데 사용했으므로 그 다음 인덱스인 2부터 시작
N줄만큼 반복시키면서, 한줄을 row에 Mx3개수만큼 존재하므로, 한개씩 뽑아내서 int화 시킨 후 []에 담아주기
그래서 append매서드로 각각 넣어주면 각 요소에 [2][3] 이런식으로 접근해서 원하는 값을 뽑아낼 수 있음
한 줄 읽으면 Mx3이후의 인덱스가 다음 줄이므로 index += Mx3추가

# 새롭게 이진화시킨 화면 배열(255 or 0) 초기 값
binary_image = [[0]*M for _ in range(N)]

# N만큼 반복하기(줄)
for i in range(N):
  # M만큼 반복하기(칸) - 3개의 합산평균이기에 3*M해줄 필요 없음
  for j in range(M):
    R = pixels[i][j*3]
    G = pixels[i][j*3+1]
    B = pixels[i][j*3+2]
    # 3숫자의 평균 값
    average = (R+G+B) / 3
    # 삼항 연산자
    binary_image[i][j] = 255 if average >= T else 0

binary_image를 0으로 구성된 배열로 만들어 놓은 후, RGB의 합산의 평균 값이 T보다 크거나 작거나를 비교해서 255or 0으로 바꿔주기 위한 초기 값 세팅
N줄과 M칸만큼 반복시키며 RGB를 하나씩 뽑아내서 average에 3개를 더한 값의 평균 값을 넣어주고, 앞에 말한 조건을 실행시킴

# 물체 탐색 BFS 함수
def bfs(start_x, start_y):
  # 초기 값 큐에 추가
  queue = deque([(start_x, start_y)])
  # 해당 위치는 True로 변환
  visited[start_x][start_y] = True
  # queue에 값이 있는 동안 계속 반복
  while queue:
    # 최초 값 뽑아내기(왼쪽에서)
    x, y = queue.popleft()
    # 상하좌우 값
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    
    for dx, dy in directions:
      # 기존 값에 새로운 위치 반영한 결과
      nx, ny = x + dx, y + dy
      # N,M범위 안에서 한번 체크한 곳 제외, 255 숫자가 존재할시 
      if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and binary_image[nx][ny] == 255:
        # 방문 표시
        visited[nx][ny] = True
        # 큐에 추가
        queue.append((nx, ny))

BFS로 물체 탐색
queue에는 초기로 넣어줄 startX,Y를 튜플 형식으로 넣어줌
튜플로 넣기 위해선 []안에서 ()를 사용해야 하나의 요소로 담을 수 있음
이미 binary_image 배열이 RGB를 하나로 뭉친 값의 배열이므로, 배열의 칸수가 /3으로 줄어들었고, 그 length와 동일한 배열로 이어있는지, 떨어져있는지 물체의 크기를 한개씩 찾아가며 가늠하기 위한 boolean 배열인 visited = [[False]*M for in range(N)]로 선언해주기
그 후, 큐가 빌때까지 while반복문 반복
일단 최초 x,y를 popleft로 뽑아내고, 상하좌우 4방향 검사 진행, 그 후 조건은 N,M범위 안에서, 255값을 가리키며, boolean이 True가 아닌(한번도 방문해서 체크하지 않음) 4가지 조건이 다 참이라면?? visited에 True로 방문체크, queue엔 새로 변경한 값 담아주고 계속 반복 실행

# 방문 여부 초기화
visited = [[False]*M for _ in range(N)]

# 물체 개수 초기화
object_count = 0

for i in range(N):
  for j in range(M):
    if binary_image[i][j] == 255 and not visited[i][j]:
      bfs(i, j)
      object_count += 1

print(object_count)

그 후 모든 값을 체크해서 반영이 되었다면, 물체 하나당 +1을 해주는 로직인데, 이 부분이 생각보다 이해하기 어려웠다.
일단, 이진화된 화면에서 255픽셀이 맞는지 확인하고, 현재 픽셀을 아직 방문하지 않았다면(false)라면??
현재 픽셀이 물체의 일부고, 물체 탐색을 시작시켜줘야 한다.

근데 물체가 크든 작든, for문안에서 작동하는 로직이기에,
i,j로 시작해서 하나의 물체에 대한 연결탐색이 끝났을때, +1로 카운팅을 해준다
그 후에는 i+1, j+1 이런식으로 작동할 때, 이미 방문한적이 있는 곳은 True로 visited가 변환되므로, 체크해주지 않는다.

즉, 물체가 크든, 작든 하나의 물체로 인식 시켜줄 수 있는 로직인 것이다.

참... 문제가 뜯어보면 이해가 되지만 이걸 혼자서 처음부터 푸는건 너무너무 어렵다 지금의 나에겐.. 그러나 포기하지말자!! 재밌잖아 한잔해!!

profile
규갓 God Gyu
웹 개발자 되고 시포용
이전 포스트

[백준] 침투 (Python)

다음 포스트

[백준] 음식물 피하기 (Python)

0개의 댓글