[JS] 프렌즈4블록

어렵네요. 완전탐색테스트 케이스 생각하기 힘들어서 더 힘든듯... ㅎ

 

완전탐색에 대한 감이 잡혔다고 생각했는데 항상 미숙한 점이 나와서 아쉽네요. 다음 노드에서 계산하면 되는 걸 지금 노드에서 굳이 계산해주느라고 시간도 그리고 메모리도 날려먹었습니다.

일단 같이 한번 보시죠!

---

문제 요약

같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

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

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

 

테스트케이스

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

 

접근 방법

전 처음에 dfs 같은 경로를 생각했었는데,

잘 생각해보니 굳이 뒤로 돌아가야하나? 라는 생각이 들더라구요. 일단 기본적으로 [0, 1], [1, 0], [1, 1]을 검사하고 다 같은 모양일 때 카드를 터치면 된다고 생각했습니다.

 

조심하셔야할 점은 블록이 결합되어서 터칠 때는 무조건 2X2 형태라는 겁니다. 그래서 일단 터진다면, 각 노드에서 또 2X2를 만족하는지 확인하고 가능한 최대한의 크기로 터뜨려야합니다.

 

터뜨리는 블록을 묶는 방법

1. 어떤 노드에서 단위 거리([0, 1], [1, 0], [1, 1]) 만큼 떨어져 있는 좌표의 값들을 불러온다.
2. 단위거리를 더해준 노드가 현재 board의 m, n을 넘어가진 않는지 확인한다.
3. 모든 노드가 같은 캐릭터인지 확인한다.
   1. 만약 같은 캐릭터라면  일단 터질 예정이니 어떤 배열에 좌표를 넣어준다.
      (※ 먼저 공백 문자로 치환하지 않습니다. 최대한 묶어서 한번에 바꿔줘야하기 때문에 모든 탐색이 완료되고 나서 처리해줘야합니다.)
   2. 다른 캐릭터라면 그냥 바로 다음 루프로 넘어가 준다.
4. 터질 좌표를 모은 배열을 순회하면서 블록을 바꿔준다.
   이때 그냥 없애주는 거보다 "-" 같은 걸로 바꿔주는게 정신건강에 좋다.
5. board를 정렬해준다. "-"는 뒤로 보내준다.

 

이 과정을 더 이상 터질 노드가 없어질 때 까지 반복해주면 원하는 최종 값을 얻어낼 수 있습니다.

정답 코드 같이 보시죠!

 

정답 코드

function solution(m, n, board) {
//graph: board의 pivot 테이블. 각 열을 stack으로 관리하기 위함.
    let graph = Array.from({length: n}, () => []);
    board.forEach((line, i) => {
        for (let j = 0; j < n; j++) {
            graph[j].push(line[j]);
        }
    });
    // 2X2 전용 단위 거리
    const dx = [1, 0, 1];
    const dy = [0, 1, 1];
    while (fullSearch()) {
        graph = graph.map((row) => {
        //"-"를 뒤로 보내는 정렬 방법.
            row.sort((a, b) => {
                if (a === "-") return -1;
                else return 1;
            });
            return row;
        });
    }
    return graph.flatMap(v => v).filter(v => v === "-").length;
    
    function fullSearch() {
        let isChanged = false;
        const explodes = [];
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < graph[i].length; j++) {
                if (graph[i][j] === "-") continue;
                const [x, y] = [i, j];
                const blocks = [];
                for (let k = 0; k < 3; k++) {
                    const nx = x + dx[k];
                    const ny = y + dy[k];
                    if (nx < n && ny < m) {
                        if (graph[x][y] === graph[nx][ny]) blocks.push([nx, ny]);
                        else break;
                    } else break;
                }
                if (blocks.length === 3) {
                    explodes.push([x, y]);
                    explodes.push(...blocks);
                }
            }
        }
        if (explodes.length >= 4) {
            isChanged = true;
            explodes.forEach(v => {
                const [x, y] = v;
                graph[x][y] = "-";
            });
        }
        return isChanged;
    }
}

 

팁 1. board를 그대로 안쓰고 행-열을 바꿔준 이유

let graph = Array.from({length: n}, () => []);
board.forEach((line, i) => {
    for (let j = 0; j < n; j++) {
        graph[j].push(line[j]);
    }
});

 

각 캐릭터가 터질 때 열 기준으로 쭉 내려오기 때문입니다.

만약 그대로 행 기준으로 데이터를 보관하면 정말 처리가 어려워용...

 

팁 2. fullSearch의 핵심로직

...
if (graph[i][j] === "-") continue;
const [x, y] = [i, j];
const blocks = [];
for (let k = 0; k < 3; k++) {
    const nx = x + dx[k];
    const ny = y + dy[k];
    if (nx < n && ny < m) {
        if (graph[x][y] === graph[nx][ny]) blocks.push([nx, ny]);
        else break;
    } else break;
}
if (blocks.length === 3) {
    explodes.push([x, y]);
    explodes.push(...blocks);
}
...

먼저 지금 공백칸일 때 다음칸으로 넘깁니다.

이건 제가 한번 전체 탐색을 마치고 정렬을 해주기 때문에 관계없습니다. 정렬을 생략한다면, 단위거리만큼 계속 더해줘서 공백문자가 안나올 때까지 노드를 이동시켜야겠네요.

 

지금 위치 기준으로 단위 길이 안의 모든 캐릭터가 같다면 explodes 배열에 지금 위치, 그리고 나머지 위치를 넣어줍니다.

 

※ Q. 왜 fullSearch에서 갯수를 안 세어줬나요?

A. 겹치는 것들이 종종 있어서 그렇습니다. [[A, A, A], [A, A, A], [A, A, A]] 만약 이런 조합이 있으면 가운데 [1, 1] 좌표가 정말 여러번 겹칩니다. set으로 처리하고 각 좌표를 string으로 저장하는 방법도 있습니다만, 해보니 그냥 이렇게 하는게 더 빠르더라구요.

 

팁 3. 내 입맛대로 정렬하는 방법

while (fullSearch()) {
    graph = graph.map((row) => {
    //"-"를 뒤로 보내는 정렬 방법.
        row.sort((a, b) => {
            if (a === "-") return -1;
            else return 1;
        });
        return row;
    });
}

fullSearch는 explodes 배열에 값이 있는지를 체크하고 있다면 true를 리턴해줍니다.

sort 안의 compare 함수를 내 입맛대로 다룰 줄 아시면 일단 코테에선 유용할 때가 많습니다.

 

오름차순 정렬할때 a - b를 쓰잖아요. 음수 값이라면 -가 앞으로 오게 됩니다.

그러므로 a 가 "-"(공백)일때 -1을 return. 그 이외라면 1을 return 해주면 되겠습니다.

 

혹시 궁금하신 분들을 위해 콘솔을 찍어보면 이런 식으로 나와용..

 

[
  [ '-', '-', 'T', 'T', 'T', 'T' ],
  [ '-', '-', '-', 'T', 'T', 'M' ],
  [ '-', '-', 'T', 'F', 'M', 'M' ],
  [ 'A', 'A', 'F', 'R', 'M', 'T' ],
  [ '-', '-', 'N', 'A', 'M', 'T' ],
  [ '-', '-', 'T', 'A', 'F', 'J' ]
]
[
  [ '-', '-', '-', '-', 'T', 'T' ],
  [ '-', '-', '-', '-', '-', 'M' ],
  [ '-', '-', 'T', 'F', 'M', 'M' ],
  [ 'A', 'A', 'F', 'R', 'M', 'T' ],
  [ '-', '-', 'N', 'A', 'M', 'T' ],
  [ '-', '-', 'T', 'A', 'F', 'J' ]
]

 

 

완전 탐색 문제는 몇 개 더 풀어봐야겠네요. 한번에 풀어본 적이 없네요.

3시간은 생각했던 것 같습니다.

 

그럼 이만!