문제
- Binary 이미지
- 각 필셀은 background pixel이거나 혹은 imgage, pixel
- 서로 연결된 image pixel들의 집합을 blob이라고 부름
- 상하좌우 및 대각방향으로도 연결된것으로 간주.
해결 방법1
-
입력
- N*N 크기의 2차원 그리드(grid)
- 하나의 좌표(x,y)
-
출력
- 픽셀(x,y)가 포함된 blob의 크기,
- (x,y)가 어떤 blob에도 속하지 않는 경우에는 0
현재 픽셀이 속한 blog의 크기를 카운트하려면
= 현재 픽셀이 image color가 아니라면
0을 반환한다.
= 현재 픽셀이 iamge color라면
- 먼저 현재 필셀을 카운트한다.(count=1)
- 현재 픽셀 중복 카운트 되는 것을 방지하기 위해 다른 색(여기선 red)으로 칠한다.
- 현재 픽셀에 이웃한 모든 픽셀들에 대해서 그 픽셀이 속한 blob의 크기를 카운트 하여 카운트에 더해준다.
= 카운터를 반환CODE1
const BACKGROUND_COLOR = 0
const IMAGE_COLOR = 1
const ALREADY_COUNTED = "@"
const N = 8
const grid = [
[1, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 1, 0, 0, 1, 0, 0],
[1, 1, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 0],
[0, 1, 0, 1, 0, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 1],
[0, 1, 1, 0, 0, 1, 1, 1],
]
function countCells(x, y) {
if (x < 0 || x >= N || y < 0 || y >= N) {
// grid 배열 밖 영역인경우
return 0
} else if (grid[x][y] != IMAGE_COLOR) {
// Image_color가 아닌 영역인 경우
return 0
} else {
// Image_color 영역인 경우
// point: 중복으로 카운팅 하는 것을 방지
grid[x][y] = ALREADY_COUNTED
return (
1 +
//북, 북동, 동, 동남, 남, 남서, 서, 북서,
(countCells(x, y + 1) +
countCells(x + 1, y + 1) +
countCells(x + 1, y) +
countCells(x + 1, y - 1) +
countCells(x, y - 1) +
countCells(x - 1, y - 1) +
countCells(x - 1, y) +
countCells(x - 1, y + 1))
)
}
}
function printGrid() {
grid.forEach(v => {
console.log(v.toString())
console.log("----------")
})
}
console.log(countCells(5, 3))
printGrid()
let gridBlob = 0
grid.forEach(row => {
row.forEach(cell => {
if (cell === "@") gridBlob++
})
})