[KAKAO RECRUITMENT] 프렌즈4 블록 풀이

프로그래머스

 

작성 코드 (1차 시도 / 통과)

function solution(m, n, board) {
    board = board.map(v => v.split(""))
    while (1) {
        const willRemove = [] // 제거할 좌표 모음
        for (let i = 0; i < m - 1; i += 1) {
            for (let j = 0; j < n - 1; j += 1) {
                if (board[i][j] && // 빈칸이 아니면 2x2 블록 확인하여 좌표를 제거 리스트에 푸시
                    board[i][j] === board[i][j + 1] &&
                    board[i][j] === board[i + 1][j] &&
                    board[i][j] === board[i+1][j+1]) {
                    willRemove.push([i, j])
                }
            }
        }
        willRemove.forEach(v => { // 사각 블록 제거
            const [x, y] = v
            board[x][y] = 0
            board[x][y + 1] = 0
            board[x + 1][y] = 0
            board[x + 1][y + 1] = 0
        })
        
        // 블록 내려주기
        for (let i = m - 1; i > 0; i -= 1) { 
            for (let j = 0; j < n; j += 1) {
                if (!board[i][j]) {
                    let f = i - 1
                    while(f >= 0) { // 깊이 탐색
                        if (board[f][j]) { // 위쪽에 모양이 존재하면 위치 교환
                            board[i][j] = board[f][j]
                            board[f][j] = 0
                            break
                        } else {
                            f -= 1
                        }
                    }
                }
            }
        }
        // 더이상 사각 블록이 없는 경우 리턴
        if (!willRemove.length) return board.flat().filter(v => !v).length
    }
}

 

구현 로직

주어진 2차원 배열을 순차적으로 돌면서 현재 좌표에서 사각 블록을 만들 수 있는 지 확인합니다. 현재 자리와 오른쪽, 아래, 오른쪽 아래 부분이 동일한 블록인지를 확인하여 동일한 경우 해당 좌표를 제거 리스트 (willRemove)에 올려둡니다.

 

이중 for문이 끝나면 제거리스트에 담긴 좌표를 확인하여 사각 블록을 제거해줍니다. 제거는 0으로 표시했습니다.

 

이제 블록을 내려줘야 하므로 다시 순차적으로 확인하여 빈 칸이 존재하면 현재 열의 맨 윗부분까지 확인하여 빈값이 아닌 모양이 있으면 그값을 빈 칸과 교환합니다. (=내려줍니다) 

 

더이상 사각 블록이 없는 경우에는 빈 값의 개수를 리턴합니다.