JavaScript를 사용하여 boggle 단어 유효성 검사

문제

Boggle 보드는 개별 문자의 2D 배열입니다. -

const board = [
   ["I","L","A","W"],
   ["B","N","G","E"],
   ["I","U","A","O"],
   ["A","S","R","L"]
];

우리는 보글보드와 문자열을 받아서 그 문자열이 보글보드에서 유효한 추측인지 확인하는 JavaScript 함수를 작성해야 합니다. 유효한 추측은 인접한 셀(가로, 세로 또는 대각선으로) 이전에 사용한 셀을 재사용하지 않습니다.

예를 들어 위의 보드에서 "LINGO" 및 "ILNBIA"는 모두 유효한 추측이지만 "BUNGIE" 및 "SINUS"는 그렇지 않습니다.

예시

다음은 코드입니다 -

const board = [
   ["I","L","A","W"],
   ["B","N","G","E"],
   ["I","U","A","O"],
   ["A","S","R","L"]
];
const guess = 'BINGO';
const checkWord = (board = [], guess = '') => {
   const numRows = board.length;
   const numCols = board[0].length;
   let queue = board.reduce((acc, row, i) => {
      row.forEach((x, j) => {
         if (x === guess[0]) {
            acc.push ( { pos: {r: i, c: j} , nextIndex: 1, path: [numCols*i + j ] } );
         }
      });
      return acc;
   }, []);
   let exploreWord = (obj, queue) => {
      let allMoves = [ {r: obj.pos.r - 1, c: obj.pos.c },
      {r: obj.pos.r + 1, c: obj.pos.c },
      {r: obj.pos.r, c: obj.pos.c - 1 },
      {r: obj.pos.r, c: obj.pos.c + 1 },
      {r: obj.pos.r - 1, c: obj.pos.c - 1 },
      {r: obj.pos.r - 1, c: obj.pos.c + 1 },
      {r: obj.pos.r + 1, c: obj.pos.c - 1 },
      {r: obj.pos.r + 1, c: obj.pos.c + 1 }];
      allMoves.forEach((o) => {
         let index = numCols * o.r + o.c;
         if (o.r >= 0 && o.r < numRows && o.c >= 0 && o.c < numCols) {
            if (board[o.r][o.c] === guess[obj.nextIndex] && !obj.path.includes(index)) {
               let cloneObj = JSON.parse(JSON.stringify(obj));
               cloneObj.pos = { r: o.r, c: o.c };
               cloneObj.nextIndex += 1;
               cloneObj.path.push(index);
               queue.push(cloneObj);
            }
         }
      });
   };
   while (queue.length > 0) {
      let obj = queue.shift();
      if (obj.nextIndex === guess.length) {
         return true;
      }
      exploreWord(obj, queue);
   }
   return false;
};
console.log(checkWord(board, guess));

코드 설명

우리가 취한 단계는 -

• 첫 번째 문자의 출현을 찾기 위해 2차원 배열을 스캔합니다.

• 그런 다음 { position, index }를 큐에 푸시하고 큐가 비어 있지 않은 동안 첫 번째 객체를 꺼냅니다.

• 그런 다음 모든 방향을 찾습니다. 셀의 문자가 word의 문자와 일치하고 셀이 재사용되지 않으면 {position, index}를 업데이트하고 queue에 추가합니다. 그렇지 않으면 객체를 버리고 일치하는 항목이 발견되거나 모두 일치하지 않으면 중지합니다.

출력

true