미로 탐색

문제

언어

  • JavaScript

문제 풀이 step 1

  • 문제에서 원하는 것은 (1, 1) 에서 (N, M) 까지 경로 중 최단 거리의 경로입니다.
  • 갈 수 없는 경우에 대해서 별다른 얘기가 없는 것을 보니 그 부분에 대한 예외 처리는 안 해도 될 것 같습니다.
  • 최단 경로를 찾을 수 있는 BFS 탐색을 이용합니다.
  • 저는 방문 처리와 거리를 동시에 계산할 수 있는 방식으로 구현했습니다.
    • 처음 (1, 1) 노드를 방문했을 때 방문했다는 의미로 값을 2 로 주었습니다.
    • 다음 노드를 방문할 때는 이전 노드의 값에 + 1 한 값을 주었습니다.
    • 이런 방식으로 방문 처리와 시작점에서 방문한 노드 까지의 거리를 기록하면서 탐색을 진행했습니다.
    • 단, 처음 (1, 1) 노드에 값을 2 로 주었기 때문에 마지막 노드에서는 - 1 을 해줘야 합니다.
    • 정답인 시작점으로부터의 거리는 arr[N][m] 에 기록되어 있습니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const START_MARK = 2;

class Dot {
	constructor(x, y) {
		this.x = x;
		this.y = y;
	}
}

const BFS = (n, m, i, j, arr) => {
	const cx = [0, 0, 1, -1];
	const cy = [1, -1, 0, 0];

	arr[i][j] = START_MARK;
	const queue = [new Dot(i, j)];
	while (queue.length) {
		const from = queue.shift();
		const NEXT_MARK = arr[from.x][from.y] + 1;

		for (let i = 0; i < 4; i++) {
			const to = new Dot(from.x + cx[i], from.y + cy[i]);

			if (
				0 <= to.x &&
				to.x < n &&
				0 <= to.y &&
				to.y < m &&
				arr[to.x][to.y] === 1
			) {
				arr[to.x][to.y] = NEXT_MARK;
				queue.push(to);
			}
		}
	}
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);

	const arr = [];
	for (let i = 1; i < n + 1; i++) {
		arr[i - 1] = input[i].split("").map(Number);
	}

	BFS(n, m, 0, 0, arr);

	// 시작을 2 부터 시작해서 - 1 해주기
	return arr[n - 1][m - 1] - 1;
};

console.log(solution(input));