[JavaScript] LeetCode BackTracking 기본 문제들(2)

gitgitWi's TIL·2021년 2월 6일
1

LeetCode도장깨기

목록 보기
3/6

Youtube 코드 없는 프로그래밍 채널의 백트래킹 playlist 따라서 관련 문제들을 풀어보았습니다.

교과서적인 문제들이지만 아직은 실력이 부족해서 모두 강의를 참고하여 JavaScript 코드로 바꾸어 해결했습니다.

강의 영상에서 하시는 것처럼, decision tree를 손으로 그려보는 습관을 가져야 할 것 같습니다.

  • 3시간 정도 헤매다가 결국 강의 영상 참고해서 해결
  • 이전 기본 문제들처럼 exit - process - recursion 구조는 동일하지만
  • 좀더 backtracking스럽게(?), 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;
};
  • 아래는, 대부분 해결했지만, 일부 Case에서 시간 초과난 코드
  • brute-force로 모든 경우의 수를 다 찾게 되고, word 첫번째 자리수를 찾고 한번 더 전체 board를 돌기 때문에 시간 초과 되지 않았을까
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

  • 전체 구조는 위 WordSearch와 비슷
  • 특정 좌표에서 행, 열, 소그룹 중복 체크 함수
  • 전체 스도쿠 board에서 아직 해결 안된 좌표 찾는 함수
  • 백트래킹 프로세스 함수
  • 특정 좌표에는 단 하나의 수만 들어갈 수 있으므로, 빈 곳 어디에서 시작하든 동일한 decision tree 만들어짐
  • 특정 좌표에 방문한 경우, 1~9 숫자 모두에 대해 대입해서 재귀로 트래킹
/**
 * 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

  • 전반적인 구조는 비슷
  • brute-force로 하나하나씩 대입해보면 작은 값에서도 시간 초과로 해결 안됨
  • 중복 체크에서 효율성을 높인 부분은 두고 두고 복습해야 할 듯; Set, row-col 좌표값 활용 등
  • 복잡한 deepCopy가 필요 없도록, 아예 row 생성시부터 문자열로 만듦
/**
 * @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;
};
profile
가볍게 TIL 남기는 velog, 꾸준히 성장하는 개발자

0개의 댓글