움직이는 미로 탈출

문제

언어

  • JavaScript

순서도

  1. 7 초 동안 BFS 탐색 수행
  2. 매 탐색마다 현재 위치에서 갈 수 있는 모든 칸 검사 후 벽 한 칸 내리기
  3. 7 초가 모두 지나 벽이 가장 아래의 행에 내려왔을 때에도 큐에 캐릭터의 위치가 남아있다면 1, 아니면 0 을 출력합니다.

문제 풀이 step 1

  • 크기가 8 x 8 인 체스판에서 탈출하는 게임이 있습니다.
  • 체스판의 모든 칸은 빈 칸 또는 벽 중 하나입니다.
  • 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 합니다.
  • 이 게임의 특징은 벽이 움직인다는 점입니다.
    • 1 초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 됩니다.
  • 캐릭터는 1 초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나 현재 위치에 서 있을 수 있습니다.
  • 이동할 때는 빈 칸으로만 이동할 수 있습니다.
  • 1 초 동안 캐릭터가 먼저 이동하고, 그 다음 벽이 이동합니다.
  • 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없습니다.

문제 풀이 step 2

  • 우리가 어렸을 때, 만화나 영화에서 뾰족한 가시로 되어있는 벽이 밀려오는 걸 생각하면, 문제를 더욱 쉽게 이해할 수 있습니다.
  • 본 문제의 가장 중요한 포인트는 결국 8 초가 지나면, 체스판에 있는 벽들은 모두 사라지게 됩니다.
  • 따라서 8 초 동안 벽에 닿지 않고, 체스판에 살아남기만 하면 무조건 가장 오른쪽 윗 칸으로 이동할 수 얘기가 됩니다.
  • 이 포인트에 유의해서 BFS 탐색을 수행해주면 되겠습니다.
  • BFS 탐색은 다음과 같은 과정으로 이루어져 있습니다.
    • 우선 가장 왼쪽 아랫 칸인 [7, 0] 에서 탐색을 시작합니다.
    • 탐색은 두 개의 큐로 나눠서 진행합니다. 이는 시간을 기준으로 단계를 나눠서 탐색을 수행하기 위함입니다.
    • 현재 큐에서 총 9 가지 방향으로 탐색을 수행합니다.
      • 9 가지 방향은 제자리, 상하좌우, 대각선 으로 이루어져 있습니다.
    • 9 가지 방향에 대해서 체스판을 벗어나는지, 벽인지, 벽이 내려올 위치인지를 검사해서 갈 수 있는 위치라면, 다음 큐에 넣어줍니다.
    • 현재 큐가 빌 때까지 탐색을 수행합니다.
    • 현재 큐가 비게되면, 현재 큐를 다음 큐로 바꿔주고, 벽을 한 칸씩 내려줍니다.
  • 탐색을 모두 마친 후, 큐가 비어있지 않다면 1 을 반환하고, 큐가 비어있다면 0 을 반환합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 본 문제를 벽부수고 이동하기 문제처럼 방문처리를 시간에 따라서 한 차원 더 추가해서 해주면, 더욱 빠르게 구현할 수 있는 문제인 것 같습니다.
  • 그리고 체스판에서 가장 위에 있는 벽보다 한 칸이라도 위에 위치하게 된다면, 무조건 가장 오른쪽 윗 칸으로 이동할 수 있다라는 확실한 조건이 있습니다.
  • 후자의 방법을 적용해봤는데, 제대로 구현을 못해서인지 계속 틀려서 이 부분에 대한 해결과 전자에 대한 방법을 추가로 작성해야겠습니다.

소스 코드

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

// 총 9 가지 방향
let dir = [
	[0, 0],
	[0, 1],
	[0, -1],
	[-1, 0],
	[1, 0],
	[-1, 1],
	[-1, -1],
	[1, -1],
	[1, 1],
];

// 체스판을 벗어나는지 검사
const isPossibleRoute = (n, m, x, y) => 0 <= x && x < n && 0 <= y && y < m;

// 벽 한 칸씩 내리기
const downWall = (arr) => {
	for (let j = 0; j < 8; j++) {
		for (let i = 7; i > 0; i--) {
			arr[i][j] = arr[i - 1][j];
		}
		arr[0][j] = ".";
	}
};

// BFS 탐색 함수
const bfs = (arr) => {
	let queue = new Queue();
	let nextQueue = new Queue();

	// 시작 위치 넣기
	queue.enqueue([7, 0]);
	let cnt = 7;
	while (!queue.isEmpty() && cnt-- > 0) {
		while (!queue.isEmpty()) {
			const [fx, fy] = queue.dequeue();

			// 총 9 가지 방향으로 탐색
			for (let i = 0; i < 9; i++) {
				const [tx, ty] = [fx + dir[i][0], fy + dir[i][1]];

				// 체스판을 벗어나는지, 벽인지, 벽이 내려올 위치인지 검사
				if (!isPossibleRoute(8, 8, tx, ty)) continue;
				if (arr[tx][ty] === "#") continue;
				if (tx - 1 >= 0 && arr[tx - 1][ty] === "#") continue;

				nextQueue.enqueue([tx, ty]);
			}
		}

		// 다음 큐로 바꿔주기
		queue = nextQueue;
		nextQueue = new Queue();

		// 벽 한 칸씩 내리기
		downWall(arr);
	}

	// queue 가 비어있지 않다면 true, queue 가 비어있다면 false
	if (!queue.isEmpty()) return true;
	return false;
};

const solution = (input) => {
	const map = input.map((v) => v.split(""));
	// 시작 위치가 벽으로 되어있다면 0 반환
	if (map[7][0] === "#") return 0;

	const isPossible = bfs(map);

	// 탐색 결과에 따라서 분기 처리
	if (isPossible) return 1;
	return 0;
};

console.log(solution(input));