Level 2️⃣ - 프렌즈 4블록

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

프로그래머스

 

🚀접근 방법

4방향 탐색을 해서 같은 요소들이 2*2 크기에 있다면 해당 좌표를 저장하고 0으로 채운다.

그리고 블록을 아래로 떨궈 빈 공간을 메꾸면 되는데 이 부분의 구현이 가장 힘들었다.

function solve(i, j, board){
    const pick = board[i][j];
    if(pick && 
       pick === board[i][j+1] &&
       pick === board[i+1][j] &&
       pick === board[i+1][j+1]) return true;
    return false;
}
function solution(m, n, board) {
    board = board.map((elem)=> elem.split(""));
    while(true){
        const find = [];
        for(let i = 0; i<m-1; i++){
            for(let j = 0; j<n-1; j++){
                if(solve(i, j, board)) find.push([i, j]);
            }
        }
        // find가 없다면 중복되는 값이 없으므로 함수를 종료한다.
        if(!find.length) return board.flat().filter((elem)=>!elem).length;        
        find.forEach(([a, b])=> {
            board[a][b] = 0;
            board[a][b+1] = 0;
            board[a+1][b] = 0;
            board[a+1][b+1] = 0;
        });
        
        for(let y = m-1; y>=0; y--){
            for(let x = 0; x<n; x++){
                for(let i = y-1; i>=0; i--){
                    let cur = board[y][x];
                    if(cur) break;
                    let next = board[i][x];
                    if(next){
                        board[y][x] = next;
                        board[i][x] = 0;
                        break;
                    }
                }
            }
        }
    }
}

 

빈공간을 메꿔 재정렬하는 부분을 살펴보자.

아래에서 위로 탐색하면서 현재 위치에 문자가 떨어져야되는지를 확인해야한다.

현재 위치에 문자가 있다면 현재 위치로 문자가 떨어질 수 없다. 그래서 다음 요소로 순회가 넘어가야한다.

만일 현재 위치에 0이 있고 현재 위치의 위에 있는 next 위치에 문자가 있으면 next에 있는 문자는 현재 위치에 떨어져야한다. 그래서 현재 위치를 next 위치의 문자로 바꾸고 next 위치에는 0을 넣어준다. 이렇게 2차원배열을 쭉 탐색하면 모든 배열에 비어있는 부분을 메꿀 수 있다.

 

결국 비어있는 공간을 메꾸는 것이 이 문제를 해결하냐 마냐의 키포인트였다. 까다로운 구현인 만큼 힘들었지만 새로운 방법을 익힐 수 있어서 재밌었다. 이 문제는 두 세번 스스로 구현해보면서 완벽히 익혀놔야겠다.