[JavaScript] 프로그래머스 - 블록게임

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42894

프로그래머스

 

 

[풀이]

 

초기 세팅

1. 각 블록으로 만들 수 있는 직사각형의 좌표와 블록번호를 저장합니다.

• block 배열에 [블록번호, x1, y1, x2, y2]형태로 저장합니다. 이때 해당 블록은 다음과 같습니다.

(x1, y1)		(x1, y2)
(x2, y1)		(x2, y2)

• block 배열의 어느 index에 블록번호가 저장되어 있는지 확인하기 위해 Map을 활용해 (key = 블록번호, value = 해당 블록번호의 정보가 담긴 block의 index) 형태로 저장합니다.

2. 1X1형태의 검은 블록을 채워주는 dropBlock 함수를 선언합니다.

• board를 탐색하며 검은 블록이 들어갈 수 있는 위치에 -1을 넣는 과정을 반복합니다.
• 이때, 각 열마다 0~board.length-1까지 블록이 있는 곳까지 아래와 같이 갱신합니다.

 

풀이 과정

1. removeBlock 함수를 통해 삭제할 수 있는 블록을 지웁니다.

• 우선, dropBlock 함수를 호출하여 1X1형태의 검은 블록을 채웁니다.
• map을 탐색하며 value(블록 정보의 index) 를 통해 block 배열에서 [idx, x1, y1, x2, y2] 값을 가져옵니다.
• 블록 정보로 만들 수 있는 직사각형에 0이나 다른 블록번호가 있다면 지울 수 없으로 건너뜁니다.
• 지울 수 있는 블록이라면 isChange, answer, block을 갱신하고 map에서 delete연산을 통해 블록번호를 지웁니다. (블록이 있던 위치의 board값을 0으로 갱신)
• isChange가 true라면 board가 갱신되었기 때문에 removeBlock 함수를 재귀호출 합니다.

 

따라서 removeBlock 함수의 재귀호출이 끝나면 answer에 지워진 블록의 개수가 저장됩니다.

 

[코드]

function solution(board) {
    var answer = 0;
    
    // [idx, x1, y1, x2, y2];
    const block = [];
    const map = new Map();
    
    for(let i=0;i<board.length;i++) {
        for(let j=0;j<board.length;j++) {
            if(board[i][j] > 0 && !map.has(board[i][j])) {
                let x1, y1, x2, y2;
                let idx = board[i][j];
                x1 = i;
                x2 = i;
                y1 = Infinity;
                y2 = -Infinity;
                for(let k=i;k<board.length;k++) {
                    if(!board[k].includes(idx)) {
                        break;
                    }
                    x2 = k;
                    y1 = Math.min(y1, board[k].indexOf(idx));
                    y2 = Math.max(y2, board[k].lastIndexOf(idx));
                }
                map.set(idx, block.length);
                block.push([idx, x1, y1, x2, y2]);  
            }
        }
    }

    const dropBlock = () => {
        for(let i=0;i<board.length;i++) {
            for(let j=0;j<board.length;j++) {
                if(board[j][i] > 0) {
                    break;
                }
                board[j][i] = -1;
            }
        }
    }
    
    const removeBlock = () => {
        let isChange = false;
        if(map.size === 0) {
            return;
        }
        
        dropBlock();
        
        map.forEach((value, key) => {
            const [idx, x1, y1, x2, y2] = block[value];
            let rm = true;
            for(let i=x1;i<=x2;i++) {
                for(let j=y1;j<=y2;j++) {
                    if(board[i][j] !== idx && board[i][j] >= 0) {
                        rm = false;
                        break;
                    }
                }
            }
            // 지울 수 있는 블록임
            if(rm) {
                isChange = true;
                for(let i=x1;i<=x2;i++) {
                    for(let j=y1;j<=y2;j++) {
                        board[i][j] = 0;
                    }
                }
                map.delete(idx);
                answer++;
            }
        })
        
        if(isChange) {
            removeBlock();
        }
    }
    
    removeBlock();
    
    return answer;
}