Programmers 2020 카카오 인턴십 경주로 건설

function solution(board) {
	let answer = Number.MAX_VALUE;

	const directions = {
		top: [0, -1],
		down: [0, 1],
		left: [-1, 0],
		right: [1, 0],
	};

	const start = new Node(0, 0, 'init', 0);

	const q = new Queue();
	q.enqueue(start);
	const n = board.length;

	while (!q.isEmpty()) {
		const current = q.dequeue();
		if (current.x === n - 1 && current.y === n - 1) {
			answer = answer > current.cost ? current.cost : answer;
			continue;
		}

		Object.entries(directions).forEach(([direction, value]) => {
			const next = new Node();
			next.x = current.x + value[0];
			next.y = current.y + value[1];
			next.direction = direction;

			if (isOutBoard(next.x, next.y, n)) {
				return;
			}
			if (isWall(next.x, next.y, board)) {
				return;
			}
			if (isBackward(current.direction, direction)) {
				return;
			}

			if (current.direction === 'init' || current.direction === direction) {
				next.cost = current.cost + 100;
			} else if (current.direction !== direction) {
				next.cost = current.cost + 600;
			}

			if (board[next.y][next.x] === 0) {
				board[next.y][next.x] = next.cost;
				q.enqueue(next);
			} else if (board[next.y][next.x] >= next.cost) {
				board[next.y][next.x] = next.cost;
				q.enqueue(next);
			}
		});
	}

	return answer;
}

function isOutBoard(x, y, range) {
	if (x < 0 || y < 0) {
		return true;
	}
	if (x > range - 1 || y > range - 1) {
		return true;
	}
	return false;
}

function isWall(x, y, board) {
	return board[y][x] === 1;
}

function isBackward(cur, next) {
	if (cur === 'left' && next === 'right') {
		return true;
	}
	if (cur === 'right' && next === 'left') {
		return true;
	}
	if (cur === 'top' && next === 'down') {
		return true;
	}
	if (cur === 'down' && next === 'top') {
		return true;
	}
	return false;
}

class Queue {
	constructor() {
		this._arr = [];
	}
	enqueue(item) {
		this._arr.push(item);
	}
	dequeue() {
		return this._arr.shift();
	}
	isEmpty() {
		return this._arr.length === 0;
	}
}

class Node {
	constructor(x, y, direction, cost) {
		this.x = x;
		this.y = y;
		this.direction = direction;
		this.cost = cost;
	}
}

function solution(board) {
	let answer = Number.MAX_VALUE;

	const directions = {
		top: [0, -1],
		down: [0, 1],
		left: [-1, 0],
		right: [1, 0],
	};

	const start = new Node(0, 0, 'init', 0);

	const q = new Queue();
	q.enqueue(start);
	const n = board.length;

	while (!q.isEmpty()) {
		const current = q.dequeue();
		if (current.x === n - 1 && current.y === n - 1) {
			answer = answer > current.cost ? current.cost : answer;
			continue;
		}

		Object.entries(directions).forEach(([direction, value]) => {
			const next = new Node();
			next.x = current.x + value[0];
			next.y = current.y + value[1];
			next.direction = direction;

			if (isOutBoard(next.x, next.y, n)) {
				return;
			}
			if (isWall(next.x, next.y, board)) {
				return;
			}
			if (isBackward(current.direction, direction)) {
				return;
			}

			if (current.direction === 'init' || current.direction === direction) {
				next.cost = current.cost + 100;
			} else if (current.direction !== direction) {
				next.cost = current.cost + 600;
			}

			if (board[next.y][next.x] === 0) {
				board[next.y][next.x] = next.cost;
				q.enqueue(next);
			} else if (board[next.y][next.x] >= next.cost) {
				board[next.y][next.x] = next.cost;
				q.enqueue(next);
			}
		});
	}

	return answer;
}

function isOutBoard(x, y, range) {
	if (x < 0 || y < 0) {
		return true;
	}
	if (x > range - 1 || y > range - 1) {
		return true;
	}
	return false;
}

function isWall(x, y, board) {
	return board[y][x] === 1;
}

function isBackward(cur, next) {
	if (cur === 'left' && next === 'right') {
		return true;
	}
	if (cur === 'right' && next === 'left') {
		return true;
	}
	if (cur === 'top' && next === 'down') {
		return true;
	}
	if (cur === 'down' && next === 'top') {
		return true;
	}
	return false;
}

class Queue {
	constructor() {
		this._arr = [];
	}
	enqueue(item) {
		this._arr.push(item);
	}
	dequeue() {
		return this._arr.shift();
	}
	isEmpty() {
		return this._arr.length === 0;
	}
}

class Node {
	constructor(x, y, direction, cost) {
		this.x = x;
		this.y = y;
		this.direction = direction;
		this.cost = cost;
	}
}