[프로그래머스][LEVEL2] [1차] 프렌즈4블록

# 문제 원문

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

초기 배치를 문자로 표시하면 아래와 같다.

TTTANT RRFACC RRRFCC TRRRAA TTMMMF TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력 형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예제

m / n / board / answer

4	5	["CCBDE", "AAADE", "AAABF", "CCBBF"]	14
6	6	["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]	15

예제에 대한 설명

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

해설 보러가기

 

# 문제 풀이

가볍게 보고 접근 했다가. 고생한 문제이다. 테스트케이스 10번이 사고의 틈을 꿰뚫는 느낌으로 느낀점이 많다. 입력 받은 board는 m과 n크기 만큼의 가득 찬 문자열 배열이다. 편의를 위해서 board를 2차원 배열로 변경한후, 따로 터진 블록을 체크할 해시 테이블(key, value) 형태의 자료구조를 하나 선언해준다. 단순히 객체를 써도 되지만 Map이 이터러블 객체라서 배열로 변환시 빠르므로 맵을 선언해줬다. 그후 2차원 배열 board를 순회하면서 조건에 맞는 블록들을 체크해서 터트리고 블록들을 정리하고 다시 체크해서 터트리는 과정을 더 이상 터트릴 블록이 없을때 까지 반복해서 얻어진 터트린 블록 수를 반환하면 된다.

조건에 맞는 블록들이 서로 겹칠 경우 같이 터지기 때문에 터트리는 과정 전에 먼저 터트릴 블록들을 체크하는 과정이 필요하고, 그게 끝난 후 블록들을 정리하는 과정이 필요하다. 나는 여기서 생각 없이 코드를 짜서 블록들을 정리하는 로직과, 체크해서 터트리는 로직들을 분리하지 않았는데. 그로 인해서 10번 테케를 통과 못하고 머리가 조금 아팠다. 

체크 => 폭파 => 정리 하는 로직에서 정리 로직을 한칸한칸 체크 => 폭파 를 거치면서 로직을 처리하니까 예외케이스가 생기더라. 정리 과정에서 시간의 흐름이 생겨서 조건에 맞는 조각들이 모두 모이기전에 터지는 것으로 추측된다.

결국 운동하고 다시 생각해서 풀었다. 여기서 교훈을 하나 얻었다면. 특정 루틴을 만든다면, 임의로 비슷하게 만드는게 아니라 진짜 그대로 만들어야 한다는 것이다. 처음부터 블록을 바로 가장 아래로 보냈으면 되었을 겪지 않을 문제였다. 이런 실수를 언제쯤이면 하지 않을 수 있을까?

 

# 솔루션 플로우

1. 입력 받은 board를 2차원 배열로 변경해준다.

2. 터트릴 퍼즐을 체크할 해시 자료구조 remove를 선언해준다.

3. 더 이상 터트릴 퍼즐이 없을때 까지 반복을 시작한다.

4. board의 각 col를 순회하면서 자신, 왼쪽, 자신 아래, 자신 왼쪽사선을 확인해서 remove에 해당 좌표를 체크해준다.

5. remove를 순회하면서 입력 된 좌표들을 모두 fasle 폭파 해준다.

6. false된 블록들 위의 블록들이 모두 내려올때까지 반복해서 확인한후 내려준다.

7. 모든 반복이 끝난후 board의 false 갯수를 카운팅 해서 result를 구한다.

8. 얻어진 result를 반환한다. 

1. 2차원 배열 & 반복문을 활용한 풀이

function solution(m, n, board) {
    const result = new Array(m).fill(true)
        .map((_, idx) => [...board[idx]]);
    const remove = new Map();
    // board 2차원 배열과 해시를 만든다.

    let flag = true;
    while (flag) {
        flag = false;
        for (let rdx = 0; rdx < m; rdx++) { // 조건에 맞는 블럭들을 체크한다.
            for (let cdx = 0; cdx < n; cdx++) {
                if (!result[rdx + 1] || !result[rdx][cdx]) continue;
                if (result[rdx][cdx] !== result[rdx][cdx + 1]) continue;
                if (result[rdx][cdx] !== result[rdx + 1][cdx]) continue;
                if (result[rdx + 1][cdx] !== result[rdx + 1][cdx + 1]) continue;
                remove.set(`${rdx}:${cdx}`, [rdx, cdx]);
                remove.set(`${rdx}:${cdx + 1}`, [rdx, cdx + 1]);
                remove.set(`${rdx + 1}:${cdx}`, [rdx + 1, cdx]);
                remove.set(`${rdx + 1}:${cdx + 1}`, [rdx + 1, cdx + 1]);
                flag = true;
            }
        }

        Array.from(remove.values()).forEach((xy) => { // 체크한 블럭을 터트린다.
            result[xy[0]][xy[1]] = false;
        });
        while (flag) { // 터진 블럭들을 정리한다.
            flag = false;
            for (let rdx = 1; rdx < m; rdx++) {
                for (let cdx = 0; cdx < n; cdx++) {
                    if (!result[rdx][cdx]) {
                        result[rdx][cdx] = result[rdx - 1][cdx];
                        result[rdx - 1][cdx] = false;
                        if (result[rdx][cdx]) flag = true;
                    }
                }
            }
        }

        if (remove.size > 0) flag = true; // 터진 블럭이 있을 경우 다시 한번 확인한다.
        remove.clear();
    }
    return result.reduce((result, row) => {
        row.forEach((col) => !col && result++);
        return result;
    }, 0);
}