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

문제

블록게임

프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.

이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.

프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.

게임규칙

아래 그림과 같이 1×1 크기의 블록을 이어 붙여 만든 3 종류의 블록을 회전해서 총 12가지 모양의 블록을 만들 수 있다.

1 x 1 크기의 정사각형으로 이루어진 N x N 크기의 보드 위에 이 블록들이 배치된 채로 게임이 시작된다. (보드 위에 놓인 블록은 회전할 수 없다). 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.

플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록은 항상 맵의 한 칸에 꽉 차게 떨어뜨려야 하며, 줄에 걸치면 안된다.
이때, 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.

예를 들어 검은 블록을 떨어뜨려 아래와 같이 만들 경우 주황색 블록을 없앨 수 있다.

빨간 블록을 가로막던 주황색 블록이 없어졌으므로 다음과 같이 빨간 블록도 없앨 수 있다.

그러나 다른 블록들은 검은 블록을 떨어뜨려 직사각형으로 만들 수 없기 때문에 없앨 수 없다.

따라서 위 예시에서 없앨 수 있는 블록은 최대 2개이다.

보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라.

---

접근

(0,0) 에서 (h,w)까지 모든 경로를 탐색함

(0,0)에서 탐색할 때는 2가지를 봐야함

1. 2*3 블록 확인 ex) (0,0) (0,1) (1,0) (1,1) (2,0) (2,1)
2. 3*2 블록 확인 ex) (0,0) (0,1) (0,2) (1,0) (1,1), (1,2)

1,2번을 확인해서 0(빈칸) 2개, 다른 블록 4개로 이루어져 있는지, 2종료의 블록이 들어있는지 확인

해당 조건을 만족해야만 직사각형을 만들어 부실 수 있음

해당 조건을 만족한다면, 0에다가 블록을 떨어 뜨릴 수 있는지 확인해야함(위로 쭉 올라가면서 0이 아닌 값이 있으면 fail)

0인 빈칸 2칸에 블록을 내려 다 채울 수 있다면 성공,asnwer++ 한 후에, 다시 처음 (0,0)으로 돌아가서 변화가 없을 때까지 탐색.

---

코드

function solution(board) {
    var answer = 0;
    let changeFlag = true;;
    let [h,w] = [board.length, board[0].length];
    
    const find = (r,c,width,height) => {
        let check = new Map();
        let save = -1;
        let zeroPos = [];
        for(let i=r; i<r+height; i++){
            for(let j=c; j<c+width; j++){
                if(i<0 || j<0 || i>=h || j>=w) return false;
                if(check.has(board[i][j])) check.set(board[i][j],check.get(board[i][j])+1);
                else check.set(board[i][j],1);
                if(board[i][j] !== 0) save = board[i][j];
                if(board[i][j] === 0) zeroPos.push([i,j]);
            }
        }
				//2종류의 블록이 있는가?
        if([...check].length !== 2) return false;
				//빈칸이 2개인가?
        if(check.get(0) !== 2) return false;
				//빈칸외 블록이 4개 있는가?
        if(check.get(save) !== 4) return false;
        //세로경로에 장애물 없는지 확인
        for(let [i,j] of zeroPos){
            while(i!==-1){
                if(board[i][j] ==0) i--;
                else return false;
            }
        }
        //직사각형 만들었으므로 0으로 다 교체.
        for(let i=r; i<r+height; i++){
            for(let j=c; j<c+width; j++){
                board[i][j] = 0;
            }
        }
        changeFlag = true;
        return true;
    }
    //변화가 있을때 마다 처음부터 다시 검사함.
    while(changeFlag){
        changeFlag = false;
        for(let r=0; r<h; r++){
            for(let c=0; c<w; c++){
								//2*3이 성공했다면, 3*2는 볼 필요없음.
                if(find(r,c,2,3)){
                    answer++;
                    continue;
                }
                find(r,c,3,2)? answer++:'';
            }
        }
    }
    return answer;
}

---

주의

index관리