[JavaScript]Let Code BackTracking基本問題(2)
プレイリストのトレースバック Youtubeコードのないプログラミングチャンネルが問題を解いた.
教科書的な問題ですが、実力不足のためレッスンを参考にしてJavaScriptコードで置き換えました.
授業中のビデオのように、手で意思決定木を描く習慣を身につけるべきだと思います.
3時間くらいうろうろして、最後にビデオを参考に を解決しました以前の基本的な問題と同様に、 もう少し遡って(?)、再帰部添加 の下では、ほとんどが解決されたが、場合によってはタイムアウトコード 暴力、すべての状況の数はすべて探し当てて、wordの最初の桁数、もう一度全体を回して、タイムアウトしたのではないでしょうか、 全体の構造は上のWordSearchに似ています 特定の座標の下の行、列、およびグループの繰り返しチェック関数 全数独板上で未解決の座標ルックアップ関数 遡及プロセス関数 特定の座標は1つの数しかないので、どこからでも同じ決定ツリー を作成することができる.の特定の座標にアクセスした場合、すべての数値1～9を入力し、トレース に戻ります.の全体的な構造は と類似している.の暴力的な形で次々と使用され、小さな代価でもタイムアウト問題を解決することはできない .繰り返し検査で効率を高めた部分は復習しながら置くべきだ. 、Set、row-col座標値を利用は、複雑な深度コピーを必要とせず、行の作成から文字列 を作成する.
教科書的な問題ですが、実力不足のためレッスンを参考にしてJavaScriptコードで置き換えました.
授業中のビデオのように、手で意思決定木を描く習慣を身につけるべきだと思います.
79. Word Search
exit - process - recursionの構造は同じであるが、일단 check - 재귀 - 재귀에서 false 인 경우 check 해제部/**
* solution 함수
*
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
const exist = (board, word) => {
const rows = board.length;
const cols = board[0].length;
// 백트래킹을 위한 마킹 테이블 생성
const mark = Array.from({ length: rows }, () => Array(cols).fill(false));
/**
* 백트래킹 함수
*
* @param {number} row y축
* @param {number} col x축
* @param {number} idx word의 인덱스
* @returns {boolean}
*/
const bt = (row = 0, col = 0, idx = 0) => {
// 탈출 조건1 - 문자열 완성한 경우
// 조건에 맞는 결과만 재귀적으로 함수 호출하므로, idx 값만 맞으면 됨
if (idx === word.length) return true;
// 탈출 조건2 - row, col 값이 비정상이거나, 이미 방문했거나, idx에 해당하는 문자열이 아닌 경우
if (
!board[row] ||
!board[row][col] ||
mark[row][col] ||
board[row][col] !== word[idx]
)
return false;
// 일단 현재 방문한 위치에 대해 true로 마킹
mark[row][col] = true;
const nextIdx = idx + 1;
// 재귀로 그 다음 위치 탐색
// 이 중에서 그 다음 문자열을 찾게 되면 재귀 계속 진행
if (
bt(row + 1, col, nextIdx) ||
bt(row, col + 1, nextIdx) ||
bt(row - 1, col, nextIdx) ||
bt(row, col - 1, nextIdx)
)
return true;
// 그 다음 문자열을 찾지 못한 경우 백트래킹하고 false 리턴
mark[row][col] = false;
return false;
};
// board[0][0]부터 탐색 시작
// forEach 보다 단순 for-loop이 좀더 빠름
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
if (bt(row, col, 0)) return true;
}
}
return false;
};const exist = (board, word) => {
const m = board.length;
const n = board[0].length;
const first = word[0];
const firstIdxs = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === first) firstIdxs.push([i, j]);
}
}
if (firstIdxs.length === 0) return false;
const ways = [
[0, 1],
[-1, 0],
[0, -1],
[1, 0],
];
let isFound = false;
firstIdxs.map((start) => {
const findNext = (current, wIdx = 0, visited = {}) => {
if (wIdx === word.length - 1) {
isFound = true;
return;
}
const [cy, cx] = current;
visited[`${cy}${cx}`] = true;
ways.forEach((way) => {
const [b, a] = way;
const newY = cy + b;
const newX = cx + a;
if (
board[newY] &&
board[newY][newX] &&
!visited[`${newY}${newX}`] &&
board[newY][newX] === word[wIdx + 1]
) {
findNext([newY, newX], wIdx + 1, { ...visited });
}
});
};
findNext(start);
});
return isFound;
};
// 시간 초과 나는 Case
console.log(
exist(
[
[
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
],
// ...중간 생략...
[
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"a",
"b",
],
],
"baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
)
);37. Sudoku Solver
/**
* solution 함수
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
const solveSudoku = (board) => {
const SIZE = 9;
const rangeSize = Array(SIZE).fill(1);
const empty = ".";
// Y축 탐색
const checkAxisY = (target, col) => {
for (const i in rangeSize) {
if (board[i][col] === target) return false;
}
return true;
};
// X축 탐색
const checkAxisX = (target, row) => {
for (const j in rangeSize) {
if (board[row][j] === target) return false;
}
return true;
};
// 소그룹 탐색
const checkGroup = (target, row, col) => {
const rowGroup = Math.floor(row / 3) * 3;
const colGroup = Math.floor(col / 3) * 3;
for (let rg = rowGroup; rg < rowGroup + 3; rg++) {
for (let cg = colGroup; cg < colGroup + 3; cg++) {
if (board[rg][cg] === target) return false;
}
}
return true;
};
// 전체 board에서 아직 empty인 좌표 탐색
const findEmpty = () => {
for (const row in rangeSize) {
for (const col in rangeSize) {
if (board[row][col] === empty) return [row, col];
}
}
return [SIZE, SIZE];
};
/**
* 백트래킹 함수
* @param {number} row y좌표
* @param {number} col x좌표
* @param {string} target 해당 좌표에 대입할 숫자 문자열
* @returns
*/
const bt = (row, col, target) => {
// 예외처리 1: row-col 모두 [9,9]에 도착한 경우 === 남은 empty가 없는 경우
if (row === SIZE && col === SIZE) return true;
// 예외처리 2: 정상 범위 아닌 경우, 여기서는 findEmpty 함수 있어서 없어도 됨
if (!board[row] || !board[row][col]) return false;
// 예외처리 3: 이미 target 숫자가 존재하는 경우
if (
!checkAxisY(target, col) ||
!checkAxisX(target, row) ||
!checkGroup(target, row, col)
)
return false;
// 백트래킹 프로세스 시작
// 일단 해당 위치를 target으로 지정
board[row][col] = target;
// 다음 처리할 좌표 탐색
const [nextRow, nextCol] = findEmpty();
// 해당 좌표에서 target 숫자 대입, 재귀적으로 탐색 후 맞으면 탈출까지
for (const nextTarget in rangeSize) {
if (bt(nextRow, nextCol, `${+nextTarget + 1}`)) return true;
}
// 해당 위치에서 답 찾아지지 않으면 다시 empty로 복귀하고 false return
board[row][col] = empty;
return false;
};
// 프로세스 시작
const [startRow, startCol] = findEmpty();
for (const target in rangeSize) {
bt(startRow, startCol, `${target}`);
}
};51. N-Queens
/**
* @param {number} n 1 <= n <= 9
* @return {string[][]}
*/
const solveNQueens = (n) => {
const rangeN = Array(n).fill();
const results = [];
// column 중복 체크용 Set
const colSet = new Set([]);
// 우상향 대각선 (row + col) 중복 체크용 Set
const diagUpSet = new Set([]);
// 우하향 대각선 (row - col) 중복 체크용 Set
const diagDownSet = new Set([]);
// 특정 col에 Q 지정하여 row 생성 함수
const setRow = (col) => {
const row = Array(n).fill(".");
row[col] = "Q";
return row.join("");
};
const bt = (row, col, board = []) => {
const diagUp = row + col;
const diagDown = row - col;
if (
// exit 1: 범위 벗어난 경우
row === n ||
col === n ||
// exit 2: 중복체크
colSet.has(col) ||
diagUpSet.has(diagUp) ||
diagDownSet.has(diagDown)
)
return;
// backtracking process
// col 중복 없는 현재 row 생성, board에 추가
const currentRow = setRow(col);
board.push(currentRow);
if (board.length === n) {
results.push([...board]);
board.pop();
return;
}
// 중복 체크 위해 현재 정보 저장
colSet.add(col);
diagUpSet.add(diagUp);
diagDownSet.add(diagDown);
// 다음 row에 대해 재귀로 진행
rangeN.reduce((idx) => {
bt(row + 1, idx, board);
return idx + 1;
}, 0);
// 다른 backtracking 진행 위해 현재 정보 해제
diagUpSet.delete(diagUp);
diagDownSet.delete(diagDown);
colSet.delete(col);
board.pop();
};
rangeN.reduce((idx) => {
bt(0, idx, []);
return idx + 1;
}, 0);
return results;
};Reference
この問題について([JavaScript]Let Code BackTracking基本問題(2)), 我々は、より多くの情報をここで見つけました https://velog.io/@johnwi/JavaScript-LeetCode-BackTracking-기본-문제들2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol