알고스팟

문제

언어

  • JavaScript

순서도

  1. BFS 탐색

문제 풀이 step 1

  • 백준 1697번 - 숨바꼭질 3 풀이 와 유사하게 BFS 탐색을 통해 풀 수 있습니다.
  • 미로에 갇힌 운영진들은 빈 방 또는 벽으로 이동하며 미로를 탈출해야 합니다.
  • 이 때, 빈 방으로 이동하는 경우와 벽으로 이동하는 경우는 서로 다르게 구현해야 합니다.
    • 왜냐하면,
    • BFS 탐색은 한 단계씩 순서대로 나아가며 탐색을 실시합니다.
    • 근데 미로 속에서 움직일 때, 빈 방으로 이동하는 경로와 벽으로 이동하는 경로가 다른 단계이기 때문입니다.
      • 빈 방으로 이동할 때는 어떤 비용도 들지 않습니다. 하지만 벽으로 이동할 때는 벽을 부수는 비용이 발생합니다.
      • 그래서 두 경로를 구별할 수 있고, 현재 갈 수 있는 모든 빈 방이 한 단계가 됩니다. (비용이 동일하므로)
      • 그리고 벽을 부수는 경우가 다음 단계인 것이고, 여기에 부순 벽을 통해 갈 수 있게 된 모든 빈 방이 다음 단계에 포함됩니다.
    • 그래서 단계를 나눠보면,
      • 1 단계 : 빈 방으로 이동
      • 2 단계 : 벽으로 이동 + 부순 벽을 통해 갈 수 있는 빈 방으로 이동
      • 3 단계 : 벽으로 이동 + 부순 벽을 통해 갈 수 있는 빈 방으로 이동
      • …
    • 이런 식으로 탐색이 진행됩니다.
  • 탐색을 진행 중에 (N, M) 에 도달하면 탐색은 종료가 됩니다.
    • 저는 각 단계를 구별하기 위해서 Queue 를 두 개 쓰는 방식을 이용했습니다.
    • 그리고 미로의 각 방에 부순 벽의 개수를 저장하는 방식을 통해서 정답을 도출했습니다.

후기

  • 다시 풀어볼 문제입니다.
  • 예전에는 이해되지 않던 내용들을 이해할 수 있게 되어서 기쁩니다.

소스 코드 1

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

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

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

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

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

	dequeue() {
		if (!this.isEmpty()) return this.bucket[this.rear--];
	}
}

const isPossibleRoute = (to, n, m) =>
	0 <= to.x && to.x < m && 0 <= to.y && to.y < n;

const bfs = (arr, n, m) => {
	const visited = Array.from({length: m}, () => Array(n).fill(false));
	const cx = [0, 0, 1, -1];
	const cy = [1, -1, 0, 0];

	let queue = new Queue();
	let nextQueue = new Queue();

	let cnt = 0;
	visited[0][0] = true;
	queue.enqueue(new Dot(0, 0));

	// Queue 가 비었거나 목표 위치에 도달하면 종료
	while (!queue.isEmpty() && !visited[m - 1][n - 1]) {
		const from = queue.dequeue();

		for (let i = 0; i < 4; i++) {
			const to = new Dot(from.x + cx[i], from.y + cy[i]);
			if (!isPossibleRoute(to, n, m) || visited[to.x][to.y]) continue;

			// 방문 처리
			visited[to.x][to.y] = true;

			if (arr[to.x][to.y] === 0) {
				// 빈 방인 경우 현재 단계 Queue 에 넣기 (추가로 부순 벽 기록)
				arr[to.x][to.y] = cnt;
				queue.enqueue(to);
			} else {
				// 벽인 경우 다음 단계 Queue 에 넣기 (추가로 부순 벽 기록)
				arr[to.x][to.y] = cnt + 1;
				nextQueue.enqueue(to);
			}
		}

		// 현재 단계에서의 탐색이 종료가 된다면 Queue 를 옮겨줘서 다음 단계를 탐색
		if (queue.isEmpty()) {
			queue = nextQueue;
			nextQueue = new Queue();
			cnt += 1;
		}
	}

	return arr[m - 1][n - 1];
};

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

	const res = bfs(arr, n, m);
	return res;
};

console.log(solution(input));