문제 링크

프로그래머스 문제

풀이

BFS를 이용해서 풀어서 문제를 해결할 수 있었다.

하지만 풀이가 매끄럽지 못해 다른 분들의 풀이를 보면서 풀이를 보완하게 되었다.
중요한 점은 , 어떻게 방문한 점을 다시 방문하지 않도록 만드는가였다.
그래서 하나의 위치에 대해서 새로와 가로로 방문할 수 있는 방햐을 설정하기로 했으며,
이를 newBoard로 만들어서 구현해두었다.

코드

function solution(board) {
	let cnt = -1;
	const size = board.length;
 
	const newBoard = board.map((row) => {
		return row.map((r) => {
			if (r === 0) return [false, false];
			else return r;
		});
	});
 const checkLocation = (x1, y1, dir) => newBoard[x1][y1][dir] === false;

	newBoard[0][0][1] = true;

	const queue = [[0, 0, 1]];
	const move = [
		[-1, 0],
		[0, 1],
		[1, 0],
		[0, -1],
	];

	while (queue.length) {
		cnt++;
		let isPass = false;
		let qLength = queue.length;
		for (let i = 0; i < qLength; i++) {
			let [x1, y1, dir] = queue.shift();

			newBoard[x1][y1][dir] = true;
			let x2 = dir === 0 ? x1 + 1 : x1;
			let y2 = dir === 1 ? y1 + 1 : y1;

			if (x2 === size - 1 && y2 === size - 1) {
				isPass = true;
				break;
			}

			// 수평, 수직이동
			move.forEach((move) => {
				const nextX1 = x1 + move[0];
				const nextY1 = y1 + move[1];
				const nextX2 = x2 + move[0];
				const nextY2 = y2 + move[1];

				const periodCheck1 =
					nextX1 >= 0 && nextX1 < size && nextY1 >= 0 && nextY1 < size;
				const periodCheck2 =
					nextX2 >= 0 && nextX2 < size && nextY2 >= 0 && nextY2 < size;

				// console.log('1', nextX1, nextY1, nextX2, nextY2, periodCheck1, periodCheck2)

				if (periodCheck1 && periodCheck2) {
					if (
						newBoard[nextX1][nextY1] !== 1 &&
						newBoard[nextX2][nextY2] !== 1
					) {
						if (newBoard[nextX1][nextY1][dir] === false) {
							newBoard[nextX1][nextY1][dir] = true;
							queue.push([nextX1, nextY1, dir]);
						}
					}
				}
			});

			// 회전
			if (dir === 0) {
				if (y1 + 1 < size && y2 + 1 < size) {
					if (newBoard[x1][y1 + 1] !== 1 && newBoard[x2][y2 + 1] !== 1) {
						if (checkLocation(x1, y1, 1, newBoard)) {
							newBoard[x1][y1][1] = true;
							queue.push([x1, y1, 1]);
						}

						if (checkLocation(x2, y2, 1, newBoard)) {
							newBoard[x2][y2][1] = true;
							queue.push([x2, y2, 1]);
						}
					}
				}

				if (y1 - 1 >= 0 && y2 - 1 >= 0) {
					if (newBoard[x1][y1 - 1] !== 1 && newBoard[x2][y2 - 1] !== 1) {
						if (checkLocation(x1, y1 - 1, 1, newBoard)) {
							newBoard[x1][y1 - 1][1] = true;
							queue.push([x1, y1 - 1, 1]);
						}

						if (checkLocation(x2, y2 - 1, 1, newBoard)) {
							newBoard[x2][y2 - 1][1] = true;
							queue.push([x2, y2 - 1, 1]);
						}
					}
				}
			} else if (dir === 1) {
				if (x1 + 1 < size && x2 + 1 < size) {
					if (newBoard[x1 + 1][y1] !== 1 && newBoard[x2 + 1][y2] !== 1) {
						if (checkLocation(x1, y1, 0, newBoard)) {
							newBoard[x1][y1][0] = true;
							queue.push([x1, y1, 0]);
						}

						if (checkLocation(x2, y2, 0, newBoard)) {
							newBoard[x2][y2][0] = true;
							queue.push([x2, y2, 0]);
						}
					}
				}

				if (x1 - 1 >= 0 && x2 - 1 >= 0) {
					if (newBoard[x1 - 1][y1] !== 1 && newBoard[x2 - 1][y2] !== 1) {
						if (checkLocation(x1 - 1, y1, 0, newBoard)) {
							newBoard[x1 - 1][y1][0] = true;
							queue.push([x1 - 1, y1, 0]);
						}

						if (checkLocation(x2 - 1, y2, 0, newBoard)) {
							newBoard[x2 - 1][y2][0] = true;
							queue.push([x2 - 1, y2, 0]);
						}
					}
				}
			}
		}

		if (isPass) break;
	}

	return cnt;
}