[BOJ/백준] 21938 영상처리

import sys
from collections import deque
input = sys.stdin.readline

def bfs(x,y):

    queue = deque()
    queue.append((x,y))
    visited[x][y] = False
    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if visited[nx][ny] and arr[nx][ny] >= T:
                    visited[nx][ny] = False
                    queue.append((nx,ny))


N,M = map(int,input().split())

arr = []

for x in range(N):
    input_list = list(map(int,input().split()))
    temp = []
    for k in range(M):
        temp.append(sum(input_list[3*k:3*(k+1)]))

    arr.append(temp)

T = int(input())

T = 3*T


visited = [[True for _ in range(M)] for _ in range(N)]

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

cnt = 0
for x in range(N):
    for y in range(M):
        if arr[x][y] >= T  and visited[x][y]:
            bfs(x,y)
            cnt += 1

print(cnt)

 

 

이 문제는 처음들어올때부터 값을 계산해주는 방식으로 했다.

 

이 문제를 평균값을 구하면 float 값이 나올것 같아서, 어차피 문제에서 경계값이 정수이고,

 

한 픽셀을 구성하는 것은 3개로 고정적이므로 처음에 들어올때 열을 기준으로 3개씩 짤라주면서 그때의 합을 전부 저장하는 방식으로 했다.

 

이렇게 변형햔 배열을 가지고 BFS를 하면 되는데

 

계산의 편의성을 위해 경계값이 들어오자마자 그냥 3배를 해주었다.

 

그리고 난뒤에는 일반적인 BFS,DFS를 해주면 되는 문제이다.

 

방문을 하지않고, 경계값을 넘는 위치에 대해 bfs를 해서 인접한 픽셀들을 구하고, 함수가 끝난뒤에 개수를 늘려주었다.