본문 바로가기
카테고리 없음

[카카오2018] 프렌즈4블록

by limew 2023. 11. 18.

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

 

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


만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 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가 사용된다.

출력 형식

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

 

 

 

 

 

두번째 풀이를 추천한다

첫번째 풀이 (성공)

어찌저찌 풀긴 했지만 구현방식이 깔끔하지 않고 예외상황을 고려할게 많아 시간을 많이 소비했다

더보기

// dfs, 대문자
function isValidIndex(r, c, arr) {
  return r >= 0 && r < arr.length && c >= 0 && c < arr[r].length; /////
}

function isSquareSame(r, c, arr) {
  const right = { r, c: c + 1 };
  const rightDown = { r: r + 1, c: c + 1 };
  const down = { r: r + 1, c };
  if (
    isValidIndex(right.r, right.c, arr) &&
    isValidIndex(rightDown.r, rightDown.c, arr) &&
    isValidIndex(down.r, down.c, arr)
  ) {
    return (
      arr[r][c] === arr[right.r][right.c] &&
      arr[right.r][right.c] === arr[rightDown.r][rightDown.c] &&
      arr[right.r][right.c] === arr[down.r][down.c]
    );
  }
  return false;
}

function solution(m, n, board) {
  let answer = 0;
  const newBoard = [];
  const UPPERCASE = /[A-Z]/;
  board = board.reverse();
  // board를 왼쪽에서 오른쪽으로 떨이지게 재배열
  for (let c = 0; c < n; c++) {
    let newRow = [];
    for (let r = 0; r < m; r++) {
      newRow.push(board[r][c]);
    }
    newBoard.push(newRow);
  }
  let isRemoved = Array.from({ length: newBoard.length }, () =>
    Array.from({ length: newBoard[0].length }, () => false)
  );
  const square = [
    [0, 0],
    [0, 1],
    [1, 0],
    [1, 1],
  ];
  findSquare(newBoard);

  function findSquare(newBoard) {
    let isRemovedThisTime = false;
    // 순회하며 2x2찾기
    for (let r = 0; r < newBoard.length - 1; r++) {
      for (let c = 0; c < newBoard[r].length - 1; c++) {
        if (!newBoard[r][c]) break;
        if (!UPPERCASE.test(newBoard[r][c])) continue;

        if (isSquareSame(r, c, newBoard)) {
          for (const [dr, dc] of square) {
            if (!isRemoved[r + dr][c + dc]) {
              isRemovedThisTime = true;
              isRemoved[r + dr][c + dc] = true;
              answer++;
            }
          }
        }
      }
    }
    // 제거된게 있으면 true제거하고 또 스캔
    if (isRemovedThisTime) {
      // true 제거
      const afterRemoveBoard = [];
      for (let r = 0; r < newBoard.length; r++) {
        const temp = [];
        let removedCount = 0;
        for (let c = 0; c < newBoard[r].length; c++) {
          if (!isRemoved[r][c]) {
            temp.push(newBoard[r][c]);
          } else {
            removedCount++;
          }
        }
        afterRemoveBoard[r] = temp;
      }
      isRemoved = isRemoved.map((row) => row.filter((c) => c === false));
      findSquare(afterRemoveBoard);
    } else {
      return;
    }
  }
  return answer;
}

 

 

 

두번째풀이 (성공)

 

  1. 매칭이 있는지 확인하기 
  2. 매칭이 있다면 매칭갯수를 추가하고, 매칭된 부분은 위에서 떨어진 걸로 채운다. 채울 블록이 없으면 0으로 채운다
  3. 매칭이 없을 때까지 2번을 반복한다
  4. 총 매칭된 갯수를 리턴한다

 

순회하기

2차배열을 순회하면서 2x2 매칭이 있는지 찾는다

처음에는 ( 0,0 )에서 ( m-1, n-1 ) 까지 순회하는 걸 떠올렸는데,

(1,1) 에서 ( m, n ) 까지 순회하는 것이 더 효율적이라고 생각이 들었다. 그 이유는

 

1. 내부 for에서 매번 m-1, n-1하는 연산을 줄일 수 있다.

2. 첫번째 그림에서 오른쪽으로 이동하며 매칭을 찾을때 파란색기준점은 이미 매칭 됐거나 안 된 두 가지 경우가 있다.

하지만 두번째 그림에서 기준점은 항상 매칭이 안 된 경우이며, 이로써 기준점이 매칭이 된 지 판단할 필요 없다.

더보기

파란색 기준점에 따라 주변블록의 값도 변경하는데, 첫번째 그림에서 기준점은 매칭이 됐거나 안 됐다.

만약 이미 매칭이 됐으면 주변블록은 기준점과 같게 변하지만, 매칭이 되지 않았으면 -기준점의 값으로 변경해야한다.  따라서 첫번째 그림에서는 기준점이 음수인지 양수인지 판단해야한다. 

하지만 두번째 그림에서 기준점은 항상 양수 (아직 매칭이 안 된)로 주변블록 = -기준점이다

 

 

매칭이 있는지 확인하고 매칭된 블록 기록하기

 

처음에는 isMatched 라는 새로운 2차배열을 만들어서 매칭된 블록을 기록할까 생각했다.

하지만 이렇게는 두 개의 배열을 비교하고 두 번 수정해야하며, 어차피 매칭이 되는 방식은 하나이기 때문에 inplace하게 기존의 배열에 매칭된 블록을 기록하는 방법을 생각했다.

 

  1. 블록의 대문자를 charCodeAt으로 숫자로 변경
  2. 순회하면서 매칭이 되는지 확인한다. 4개의 절대값이 같으면 매칭이다 
    1. Math.abs는 속도가 느리므로 지양한다
  3. 매칭이 된 블록을 기록한다. 매칭이 된 값은 음수로 변경한다 (음수 = 매칭이 됐다, 양수 = 매칭이 아직 안 됌)

이런식으로 하면 기존 배열에서 매칭이 되는지 확인도 가능하고 매칭이 된 블록을 기록도 할 수 있다.

 

매칭된 블록 제거하고 빈 공간 채우기

 

매칭이 된적 있으면 매칭된 블록을 제거함과 동시에 위에서 밑으로 떨어져 빈 공간을 채워야한다.

배열의 밑row부터 위row까지 포인터 p1, p2를 이동한다.

p1은 매번 이동하고, p2는 매칭된 블록이 아니면 이동하고, 매칭 되어 빈 공간이면 다음으로 채울 블럭을 찾을때까지 빈 블럭을 기록한다.

p2가 빈 공간일때 p1이 매칭되지 않은 블럭을 발견하면 p2에 이 블럭을 채워넣는다.

 

 

위에 남은 공간은 0으로 채우기

0 = 빈 공간

 

 

전체코드

function solution(m, n, board) {
    var answer = 0;
    board = convertBoard(board)
    while(checkHasMatch(m, n, board)) {
        answer += findMatchCount(m, n, board);
    }
    return answer;
}

function convertBoard(board) {
    return board.map(row => {
        const arr = [];
        for (let i = 0; i < row.length; i++) {
            arr.push(row.charCodeAt(i));
        }
        return arr;
    });
}

function checkHasMatch(m, n, board) {
    let hasMatch = false;
    for (let r = 1; r < m; ++r) {
        for (let c = 1; c < n; ++c) {
            const block1 = board[r][c];
            const block2 = board[r][c-1];
            const block3 = board[r-1][c-1];
            const block4 = board[r-1][c];
            if (
                block1 !== 0 &&
                (block1 === block2 || block1 === -block2) &&
                (block2 === block3 || block2 === -block3) &&
                (block3 === block4 || block3 === -block4)
            ) {
                hasMatch = true;
                board[r][c] = -block1;
                board[r][c-1] = -block1;
                board[r-1][c-1] = -block1;
                board[r-1][c] = -block1;
            }
        }
    }
    return hasMatch;
}

function findMatchCount(m, n, board) {
    let matchedCount = 0;
    for (let c = 0; c < n; c++) {
        let p2 = m-1;
        for (let p1 = m-1; p1 >= 0; --p1) {
            // 매칭이 안 됐다
            if (board[p1][c] > 0) {
                board[p2][c] = board[p1][c]; // 매칭이 안 된 블록을 p2 위치로 내려준다
                p2--;
            } 
            // 매칭이 됐다
            else if (board[p1][c] < 0) {
                matchedCount++;
            }
        }
        while(p2 >= 0) {
            board[p2][c] = 0; // 빈공간
            p2--;
        }
    }
    return matchedCount;
}

 

 

티스토리툴바