벽 부수고 이동하기

문제

언어

  • JavaScript

순서도

  1. 벽을 부순 상태와 부수지 않은 상태를 구분하고, 차원을 나눠서 BFS 탐색

문제 풀이 step 1

  • N x M 의 행렬로 표현되는 맵이 있습니다.
  • 맵에서 0 은 이동할 수 있는 곳을 나타내고, 1 은 이동할 수 없는 벽이 있는 곳을 나타냅니다.
  • (1, 1) 에서 (N, M) 의 위치까지 이동하려 하는데, 이 때 최단 경로로 이동하려고 합니다.
  • 최단 경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말합니다. 이 때, 시작 칸과 끝 칸도 포함해서 셉니다.
  • 만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 됩니다.
  • 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸입니다.
  • 맵이 주어졌을 때, 최단 경로를 구해 내는 문제입니다.

문제 풀이 step 2

  • 가장 중요한 포인트는 방문 처리할 배열을 3 차원으로 작성하는 것입니다.
    • 기존에는 2 차원이면 충분했습니다.
    • 하지만 본 문제에서는 벽을 부순 상태와, 부수지 않은 상태에 따라서 차원이 나뉘기 때문에 3 차원으로 작성해야 합니다.
    • 방문처리 배열은 다음과 같은 형태를 띄게 됩니다.
      • Array[X 좌표][Y 좌표][벽을 부순 상태 or 벽을 부수지 않은 상태]
  • 그 다음 중요한 포인트는 벽을 부순 상태와 벽을 부수지 않은 상태에 따라서 탐색 방향을 바꿔주는 것입니다.
    • 벽을 부순 상태에서는 벽을 부수지 않은 상태로 바뀔 수 없습니다.
      • 벽을 부순 상태에서 탐색할 때는 벽을 부순 상태의 노드로만 탐색이 가능합니다.
    • 반면, 벽을 부수지 않은 상태에서는 벽을 부순 상태로 바뀔 수 있습니다.
      • 벽을 부수지 않은 상태에서 탐색할 때는 벽을 부수지 않은 상태의 노드로 탐색이 가능하고,
      • 또한 벽을 만나서 벽을 부수고 벽을 부순 상태의 노드로 탐색이 가능합니다.
  • 위의 두 포인트를 명심하며, 탐색 방향만 적절히 조정해주며 BFS 탐색을 수행합니다.
  • 탐색 도중 (N, M) 의 위치에 도달하게 되면, (N, M) 의 위치까지의 거리를 출력하면 정답입니다.
    • 단, 탐색을 모두 수행해도 (N, M) 의 위치에 도달하지 못하면 -1 을 출력합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
    • 문제를 어떻게 풀어야 하는지 느낌은 알겠지만, 여러 차원에서의 BFS 탐색이 그 내부에서 어떤 순서와 어떤 방식으로 탐색이 이루어지는지 명확하게 이해가 가지 않습니다.
  • 메모리와 소요시간이 너무 커서, 최대한 줄이는 작업을 많이 했습니다. 그 과정에서 느낀점을 아래에 적어봅니다.
    • 배열을 선언할 때, 앞의 차원이 작은게 더 빠릅니다.
      • Array[6][4][2] 보다 Array[2][6][4] 가 더 빨랐습니다.
      • 24 개의 노드에 2 칸을 만드는 것과 12 개의 노드에 4 칸을 만드는 것의 차이인 것 같습니다.
    • 탐색시 Queue 에 데이터를 넣을 때, 배열 형태보다 객체 형태가 더 빠릅니다.
      • Queue.enqueue([x, y, depth]) 보다 Queue.enqueue({x, y, depth}) 이 더 빠릅니다.
      • 이유는 정확하게는 모르겠습니다. 하지만 더 빠른것을 확인 했으니 앞으로는 객체 형태로 넣을 것 같습니다.

소스 코드

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

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	enqueue(item) {
		this.bucket[++this.rear] = item;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

	isEmpty() {
		return this.front === this.rear;
	}
}

const dir = [
	[0, -1],
	[0, 1],
	[-1, 0],
	[1, 0],
];

// 불가능한 경로인지 검사
const isPossibleRoute = (n, m, x, y) => 0 <= x && x < n && 0 <= y && y < m;

const bfs = (n, m, map, distance, depth, sx, sy) => {
	const queue = new Queue();

	// 시작점 처리
	queue.enqueue({depth, fx: sx, fy: sy});
	distance[depth][sx][sy] = 1;

	while (!queue.isEmpty()) {
		const {depth, fx, fy} = queue.dequeue();

		// 끝 점에 도달했다면 거리 반환
		if (fx === n - 1 && fy === m - 1) return distance[depth][fx][fy];

		// 4 가지 방향 검사
		for (let i = 0; i < 4; i++) {
			const [tx, ty] = [fx + dir[i][0], fy + dir[i][1]];

			if (!isPossibleRoute(n, m, tx, ty)) continue;

			// 벽이 아니라면,
			if (map[tx][ty] === 0) {
				// 이미 방문했다면, continue
				if (distance[depth][tx][ty] !== -1) continue;

				distance[depth][tx][ty] = distance[depth][fx][fy] + 1;
				queue.enqueue({depth: depth, fx: tx, fy: ty});
			} else {
				// 벽이라면,

				// 이미 벽을 부순 상태라면, continue
				if (depth === 1) continue;
				// 이미 방문했다면, continue
				if (distance[depth + 1][tx][ty] !== -1) continue;

				distance[depth + 1][tx][ty] = distance[depth][fx][fy] + 1;
				queue.enqueue({depth: depth + 1, fx: tx, fy: ty});
			}
		}
	}

	// 끝점에 도달하지 못했다면
	return -1;
};

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

	// 3 차원 형태의 방문 처리 배열 생성
	const distance = Array.from({length: 2}, () =>
		Array.from({length: n}, () => Array(m).fill(-1))
	);
	const result = bfs(n, m, map, distance, 0, 0, 0);

	// BFS 탐색 결과 반환
	return result;
};

console.log(solution(input));