문제 정의
보글(Boggle) 보드는 개별 문자들이 배치된 2차원 배열입니다. 예를 들어 다음과 같은 형태입니다.
const board = [ ["I","L","A","W"], ["B","N","G","E"], ["I","U","A","O"], ["A","S","R","L"] ];
이제 보글 보드와 문자열을 입력받아, 해당 문자열이 이 보드에서 유효한 추측(valid guess)인지 판별하는 JavaScript 함수를 작성해야 합니다.
여기서 유효한 추측이란 인접한 칸들을 가로, 세로 또는 대각선 방향으로 연결하여 만들 수 있는 문자열을 의미하며, 한 번 사용한 칸은 같은 단어 안에서 다시 재사용할 수 없습니다.
예를 들어 위의 보드에서는 "LINGO", "ILNBIA" 같은 문자열은 유효한 추측이지만, "BUNGIE"나 "SINUS"는 필요한 칸들이 서로 연결되어 있지 않거나 칸을 중복 사용해야 하기 때문에 유효하지 않습니다.
구현 예제
다음은 너비 우선 탐색(BFS) 방식으로 이 문제를 해결하는 코드입니다.
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차원 배열 전체를 스캔하여 찾고자 하는 단어의 첫 번째 글자가 위치한 모든 칸을 찾습니다.
큐 기반 탐색: 각 시작 위치를 {위치 정보, 다음 글자 인덱스, 지나온 경로} 형태의 객체로 큐에 삽입하고, 큐가 빌 때까지 앞에서부터 객체를 하나씩 꺼내 처리합니다.
8방향 확장: 현재 위치의 가로, 세로, 대각선 총 8개 방향을 확인합니다. 인접 칸의 글자가 단어의 다음 글자와 일치하고 아직 사용되지 않은 칸이라면 상태를 갱신하여 큐에 추가하고, 그렇지 않으면 해당 경로는 폐기합니다. 단어 길이만큼 모든 글자가 매칭되면 true를 반환하고, 모든 경우를 탐색해도 실패하면 false를 반환합니다.
실행 결과
"BINGO"는 보드에서 인접 칸들을 통해 연속적으로 만들 수 있으므로 다음과 같은 결과가 출력됩니다.
true