2차원 배열의 구현으로 떠오르는 비슷한 문제로는, 백준의 Puyo Puyo가 있다.
간단히 말하자면 [인접한 것 삭제 -> 삭제한 자리에 따라 기존 데이터 이동 -> 인접한 것 삭제 -> ...]의 반복이다.
이런 문제의 특징은, 중력에 의해서 블록의 위치가 이동한다는 것인데,
문제에서의 두번째 사진의 맨 위 그림처럼, 중간이 비어버리게 되면 위에 붕 뜬 것들이 아래로 떨어진다는 것이다.
이 부분은 문제에서 원하는 답에 따라 구현 방식이 달라질 것이다.
이번 문제의 경우, 지워진 블록의 갯수를 구해야했고, 인접한 것의 탐색을 위해 처음 배열의 크기가 끝날 때까지 동일해야 했다. 그래서 지워진 부분을 요소를 제거하는 방식이 아니라, _
라는 더미 데이터로 채워줬다.
그리고 탐색-변형의 과정이 반복되면 기존 데이터를 바로 변경해야하는지, 불변성을 유지해야하는지도 고려해야하기 때문에, 이련 류의 구현 문제는 대체로 작업마다 함수를 만들어서 불변성을 유지하는 것이 디버깅이 편하다.
각각의 함수가 의미하는 것은 다음과 같다.
findBlock
: board에서 지워져야 하는 대상의 spot을 2차원 배열 형태로 반환eraseBlock
: board와 erase spot을 받으면 해당 구역을 _
처리 해주고 중력에 의해 떨어진 board를 반환countErase
: 지워진(===_
처리된) 곳의 갯수 반환
function findBlock(board) {
const dir = [[0, 0], [0, 1], [1, 0], [1, 1]]
const eraseSpot = []
for (let i = 0; i < board.length-1; i++){
for (let j = 0; j < board[0].length-1; j++) {
const block = board[i][j];
if (block === '_') continue
let sameCount = 0;
dir.slice(1).forEach(([r, c]) => {
if (board[i+r][j+c] === block) sameCount += 1
})
if (sameCount === 3){
dir.forEach(([r, c]) => {
eraseSpot.push([i+r, j+c])
})
}
}
}
return eraseSpot
}
function eraseBlock(board, erase, m) {
erase.forEach(([r, c]) => {
board[r][c] = '_'
})
board = board.map(ele => {
let newEle = ele.join('').replaceAll('_', '').split('')
while (newEle.length < m){
newEle.push('_')
}
return newEle
})
return board
}
function countErase(board) {
let count = 0;
board.forEach((row) => {
row.forEach(cell => {
if (cell === '_') count ++
})
})
return count
}
function solution(m, n, board) {
var answer = 0;
let rotatedBd = Array
.from({length: n}, (_, nIdx) => Array.from({length: m}, (_, mIdx) => board[m-1-mIdx][nIdx]))
while (true){
const eraseSpot = findBlock(rotatedBd)
if (eraseSpot.length === 0){
break
}
rotatedBd = eraseBlock(rotatedBd, eraseSpot, m)
}
return countErase(rotatedBd);
}