벽 부수고 이동하기 2

문제

언어

  • JavaScript

순서도

  1. 벽을 부순 횟수에 따라서 상태를 나누고, 그 상태에 따라서 차원을 나눠서 BFS 탐색

문제 풀이 step 1

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

문제 풀이 step 2

  • 백준 2206번 - 벽 부수고 이동하기 풀이 에 추가로 벽을 부순 횟수에 따라서 상태를 나눠주면 됩니다.
  • 벽을 한 번만 부술 수 있었을 때는 벽을 부순 상태와 부수지 않은 상태에 따라서 탐색을 진행했습니다.
  • 반면, 이번에는 벽을 부술 수 있는 기회가 입력으로 주어집니다.
  • 입력으로 주어진 벽을 부술 수 있는 기회에 따라서 상태를 구분하고, 상태에 따라서 탐색을 진행하면 됩니다.
    • 예를 들어, 벽을 부술 수 있는 기회가 2 번 주어진다면,
      • 벽을 부수지 않은 상태에서는 벽을 부수지 않은 상태와 벽을 한 번 부순 상태로 탐색이 가능합니다.
      • 벽을 한 번 부순 상태에서는 벽을 한 번 부순 상태와 벽을 두 번 부순 상태로 탐색이 가능합니다.
      • 벽을 두 번 부순 상태에서는 벽을 두 번 부순 상태로만 탐색이 가능합니다.
  • 위의 내용을 표현하기 위해서 방문 처리할 배열을 3 차원으로 작성해야 합니다.
    • Array[X 좌표][Y 좌표][벽을 부순 횟수]
    • 저번과 달라지는 것은 배열의 3 번째 index 가 문제에서 주어진 벽을 부술 수 있는 기회에 따라서 달라진다는 점입니다.
  • 위의 내용에 따라서, 적절하게 BFS 탐색을 수행합니다.
  • 탐색 도중 (N, M) 의 위치에 도달하게 되면, (N, M) 의 위치까지의 거리를 출력하면 정답입니다.
    • 단, 탐색을 모두 수행해도 (N, M) 의 위치에 도달하지 못하면 -1 을 출력합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

소스 코드

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;
	}
}

// 4 가지 방향
const dir = [
	[-1, 0],
	[1, 0],
	[0, -1],
	[0, 1],
];

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

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

	// 시작점 처리
	queue.enqueue({depth: 0, x: 0, y: 0});
	distance[0][0][0] = 1;

	while (!queue.isEmpty()) {
		const {depth, x, y} = queue.dequeue();

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

		for (let i = 0; i < 4; i++) {
			const [tx, ty] = [x + dir[i][0], y + dir[i][1]];

			// 불가능한 경로라면
			if (!isPossibleRoute(n, m, tx, ty)) continue;

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

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

				// 벽을 부술 수 있는 기회를 모두 사용했다면 continue
				if (depth === k) continue;

				// 이미 방문했다면 continue
				if (distance[depth + 1][tx][ty] !== -1) continue;

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

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

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

	const distance = Array.from(Array(k + 1), () =>
		Array.from(Array(n), () => Array(m).fill(-1))
	);

	const result = bfs(n, m, k, map, distance);
	return result;
};

console.log(solution(input));