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

1. 문제

17679 문제 보러가기

2. 오답

function solution(m, n, board) {
    let newBoard = board.map(block => [...block]);
    
    while (true) { 
        let count = 0;
        for (let x = 0; x < m - 1; x++) {
            for (let y = 0; y < n - 1; y++) {
                if (board[x][y] === '') continue;
                if (board[x][y] === board[x][y + 1] && board[x][y] === board[x + 1][y] && board[x][y] === board[x + 1][y + 1]) {
                    newBoard[x][y] = '';
                    newBoard[x + 1][y] = '';
                    newBoard[x][y + 1] = '';
                    newBoard[x + 1][y + 1] = '';
                    count += 1;
                }
            }
        }
      
        if (count === 0) break;

        for (let x = 0; x < m - 1; x++) {
            for (let y = 0; y < n; y++) {
                if (newBoard[x + 1][y] === '') {
                    for (let i = x; i >= 0; i--) {
                        newBoard[i + 1][y] = newBoard[i][y];
                        newBoard[i][y] = '';
                    }
                }
            }
        }
        board = newBoard;
    }

    const allBoards = newBoard.reduce((acc, cur) => acc.concat(cur));
    return allBoards.filter(block => block === '').length;
}

내가 생각한 과정

1. board와 newBoard 두 개의 판을 놓는다.
2. board의 왼쪽상단부터 주변 블록을 비교한다.
   - 만약 판이 비어있으면 넘어간다.
   - 현재 블록의 오른쪽, 아래, 오른쪽아래대각선 모두 같으면 newBoard의 같은 블럭을 비운다.
   - count를 올린다.
3. count가 0인 경우, 즉 아무런 변화가 없는 경우 끝낸다.
4. newBoard의 왼쪽상단부터 아래 블록을 비교한다.
   - 아래 블록이 비어있으면 현재 블록을 아래로 옮기고 현재 위치의 블록은 비운다.
5. newBoard를 board에 복사한다.
6. 끝날 때까지 반복한다.
7. 모든 블록을 1차원 판으로 정리한다.
8. 빈 블록만 남기고 개수를 센다.

간과한 점

5단계(newBoard를 board에 복사한다.)에서 잘못된 점을 발견하였다.

board = newBoard로 배열을 복사하면 원본 배열의 값을 참조하여 주소값을 공유하기 때문에 둘 중 하나를 수정하면 다른 배열도 같이 변하게 된다.
이것을 얕은 복사라고 부른다.

얕은 복사를 해서 생긴 문제는 지워지는 조건에 만족하는 2×2 모양이 여러 개 있을 때 생긴다.

예를 들어 위의 보라색 블럭 2*3을 지워야 한다.

board[2][0]블록을 기준으로 newBoard의 블럭을 비워두었다.
이제 board[2][1]블록을 기준으로 블럭을 비워야 한다.
그런데 newBoard가 수정될 때 board도 같이 수정되었기 때문에 board[2][1]은 빈 블록 상태가 되어 반복문을 넘기게 된다.

따라서 board[2][2]와 board[3][2]는 비워지지 않고 넘어간다.

3. 최종 풀이

function solution(m, n, board) {
  let curBoard = board.map((block) => [...block]);
  let newBoard = board.map((block) => [...block]);

  while (true) {
    let count = 0;
    for (let x = 0; x < m - 1; x++) {
      for (let y = 0; y < n - 1; y++) {
        if (curBoard[x][y] === '') continue;
        if (
          curBoard[x][y] === curBoard[x][y + 1] &&
          curBoard[x][y] === curBoard[x + 1][y] &&
          curBoard[x][y] === curBoard[x + 1][y + 1]
        ) {
          newBoard[x][y] = '';
          newBoard[x + 1][y] = '';
          newBoard[x][y + 1] = '';
          newBoard[x + 1][y + 1] = '';
          count += 1;
        }
      }
    }
      
    if (count === 0) break;

    for (let x = 0; x < m - 1; x++) {
      for (let y = 0; y < n; y++) {
        if (newBoard[x + 1][y] === '') {
          for (let i = x; i >= 0; i--) {
            newBoard[i + 1][y] = newBoard[i][y];
            newBoard[i][y] = '';
          }
        }
      }
    }
      
    curBoard = newBoard.map((block) => [...block]);
  }

  const allBoards = newBoard.reduce((acc, cur) => acc.concat(cur));
  return allBoards.filter((block) => block === '').length;
}

board = newBoard가 아닌 curBoard = newBoard.map((block) => [...block])와 같이 배열을 복사한다.

map을 사용해 배열의 요소를 하나씩 복사하므로 원본 배열과 다른 주소값을 갖는 깊은 복사를 하게 된다.