[프로그래머스] 프렌즈4블록 - 자바스크립트

문제

코딩테스트 연습 - [1차] 프렌즈4블록

 

코드

function solution(m, n, board) {
  function checkBlock(x, y) {
    const block = board[x][y];
    if (x + 2 > m || y + 2 > n || !block) return false;
    for (let i = x; i < x + 2; i++) {
      for (let j = y; j < y + 2; j++) {
        if (block === board[i][j]) continue;
        return false;
      }
    }
    return true;
  }

  function removeBlock(arr) {
    arr.forEach(({ x, y}) => {
      for (let i = x; i < x + 2; i++) {
        for (let j = y; j < y + 2; j++) {
          board[i][j] = 0;
        }
      }
    });
  }

  function arrangeBlock() {
    for (let i = m - 1; i >= 0; i--) {
      for (let j = n - 1; j >= 0; j--) {
        if (board[i][j]) continue;
        let idx = i - 1;
        while (idx > -1) {
          if (board[idx][j]) {
            board[i][j] = board[idx][j];
            board[idx][j] = 0;
            break;
          } else idx--;
        }
      }
    }
  }

  board = board.map((v) => v.split(""));
  while (true) {
    let removeBlocks = [];
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        if (checkBlock(i, j)) {
          removeBlocks.push({ x: i, y: j });
        }
      }
    }
    if (!removeBlocks.length) break;
    removeBlock(removeBlocks);
    arrangeBlock();
  }

  let answer = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (!board[i][j]) answer++;
    }
  }
  return answer;
}

 

풀이

 

풀이 순서

 

없앨 블록의 크기가 2x2로 고정되어 있다.

 

1. 현재 판을 기준으로 2x2 블록을 모두 찾아서, 찾은 블록들을 한꺼번에 없애준다.

2. 판을 (m-1, n-1) => (0,0)까지 역순회하면서 블록이 없어진 공간을 찾고, 공간의 위에 있는 블록이 떨어지도록 처리한다.

3. 1, 2단계를 반복한다. 만약 1단계에서 찾은 블록이 없다면 반복을 종료한다.

4. 반복이 종료되었다면 판에서 지워진 블록 개수를 세서 출력한다.

 

 

이와 같이 의외로 방법은 간단하다.

 

블록을 찾아서 한번에 없애주고, 블록이 떨어지도록 처리하는 작업의 반복이다.

 

주석을 포함한 코드

function solution(m, n, board) {
  function checkBlock(x, y) {
    const block = board[x][y];
    if (x + 2 > m || y + 2 > n || !block) return false;
    for (let i = x; i < x + 2; i++) {
      for (let j = y; j < y + 2; j++) {
        if (block === board[i][j]) continue;
        return false;
      }
    }
    return true;
  }
  // checkBlock 함수는 확인할 x,y 좌표를 받는다.
  // 확인할 블록이 판의 범위를 벗어났거나, 블록이 0이라면(이미 지워졌다면), false
  // 블록을 확인하면서 지워질 조건 2 x 2 크기를 만족하지 않으면 false, 만족하면 true 반환

  function removeBlock(arr) {
    arr.forEach(({ x, y }) => {
      for (let i = x; i < x + 2; i++) {
        for (let j = y; j < y + 2; j++) {
          board[i][j] = 0;
        }
      }
    });
  }
  // removeBlock 함수는 x,y정보가 담긴 배열을 받아 블록을 제거해준다.
  // 각 정보를 가지고, 판의 좌표에서 원소를 0으로 바꿔준다.(필자는 0을 제거라고 취급했다.)

  function arrangeBlock() {
    for (let i = m - 1; i >= 0; i--) {
      for (let j = n - 1; j >= 0; j--) {
        if (board[i][j]) continue;
        let idx = i - 1;
        while (idx > -1) {
          if (board[idx][j]) {
            board[i][j] = board[idx][j];
            board[idx][j] = 0;
            break;
          } else idx--;
        }
      }
    }
  }
  // arrangeBlock 함수는 (m-1,n-1)부터 (0,0)까지 조회하면서, (i,j)좌표의 원소값이 0이라면 다음 작업을 수행한다.
  // (i,j)좌표 위에 있는 좌표에서 처음 원소를 발견하면 그 원소를 (i,j)로 끌어내려주고 그 공간을 빈공간으로 처리한다.
  // 이 작업을 반복하면 빈 공간 위에 있던 블록들이 모두 아래로 떨어지게 된다.

  board = board.map((v) => v.split("")); // 문자열들의 배열로 되어있는 board를 (m,n) 행렬로 만든다.
  while (true) { // 위에서 소개한 1,2번 절차를 반복해야 하므로, while문으로 시작한다.
    let removeBlocks = [];
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        if (checkBlock(i, j)) { // checkBlock함수는 2x2행렬이 존재할 때만 true 값을 반환한다. 
          removeBlocks.push({ x: i, y: j }); // 지울 블록의 정보를 배열에 넣어준다.
        }
      }
    }
    if (!removeBlocks.length) break; // 지울 블록이 없다면 while문을 종료해야 한다.
    removeBlock(removeBlocks); // 지워야 할 블록들을 모두 지운다.
    arrangeBlock(); // 블록이 아래로 떨어지도록 재배치한다.
  }

  let answer = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (!board[i][j]) answer++; // 모든 블록제거가 끝나고 판에서 0의 갯수를 세서 출력한다.
    }
  }
  return answer;
}