탈출

문제

백준 3055번 - 탈출

언어

JavaScript

순서도

고슴도치와 비버의 굴과 물의 위치 찾기
고슴도치와 물을 1 분씩 단계적으로 BFS 탐색 진행
1. 고슴도치가 비버의 굴에 도착하면 BFS 탐색 종료하고, 소요 시간 출력
2. BFS 탐색을 종료해소 고슴도치가 비버의 굴에 도착하지 못한다면, “KAKTUS” 출력

문제 풀이 step 1

티떱숲에 고슴도치 한 마리와 비버의 굴과 물이 있습니다. 그리고 빈 칸과 돌이 있습니다.
물은 1 분마다 상, 하, 좌, 우로 늘어납니다. 따라서 고슴도치는 범람하는 물을 피해서 비버의 굴로 도망쳐야 합니다.
물과 고슴도치는 돌을 통과할 수 없습니다.
고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없습니다.
그리고 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없습니다.
이 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구해야 합니다.

문제 풀이 step 2

우선, 네 개의 큐를 생성합니다.
- 고슴도치의 이동을 기록할 큐
- 고슴도치의 다음 이동을 기록할 큐
- 물의 이동을 기록할 큐
- 물의 다음 이동을 기록할 큐
우선, 주어진 티떱숲의 지도에서 고슴도치와 비버의 굴의 위치와 물의 위치를 찾습니다.
- 고슴도치의 위치를 고슴도치 큐에 넣어줍니다.
- 물의 위치를 물 큐에 넣어줍니다.
BFS 탐색을 수행합니다.
- BFS 탐색을 단계별로 진행하기 위해서 다음 이동할 좌표는 다음 큐에 넣습니다.
  - 고슴도치의 다음 이동을 기록할 큐인 nextHedgehogQueue
  - 물의 다음 이동을 기록할 큐인 nextWaterQueue
- 현재 고슴도치의 큐에서 BFS 탐색을 할 때,
  - 다음 좌표가 티떱숲을 벗어나거나, 물이 법람할 위치거나, 물이거나, 돌이거나 이미 탐색한 경로라면 탐색하지 않습니다.
  - 만일 탐색이 가능한 경로라면 시간을 기록하고, 다음 고슴도치 큐에 다음 좌표를 넣어줍니다.
- 현재 물 큐에서 BFS 탐색을 할 때,
  - 다음 좌표가 티떱숲을 벗어나거나, 물이거나, 돌이거나, 비버의 굴이라면 탐색하지 않습니다.
  - 만일 탐색이 가능한 경로라면 물로 표시해주고, 다음 물 큐에 다음 좌표를 넣어줍니다.
- 그리고 현재 고슴도치의 큐와 현재 물의 큐가 모두 비게 되면, 다음 고슴도치에 있는 좌표들을 모두 현재 고슴도치 큐에 넣어주고, 다음 물 큐에 있는 좌표들을 모두 현재 물 큐에 넣어줍니다.
- 만일 탐색 도중에 고슴도치가 비버의 굴에 도착하면, 더 이상 탐색을 하지 않고, 소요 시간을 출력합니다.
BFS 탐색을 종료해도 고슴도치가 비버의 굴에 도착하지 못한다면, “KAKTUS” 를 출력합니다.
추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

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

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

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

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

// 상, 하, 좌, 우 이동 방향
const cx = [0, 0, 1, -1];
const cy = [1, -1, 0, 0];

// 다음에 탐색할 경로가 숲을 벗어나지 않는지 검사하는 함수
const isPossibleRoute = (r, c, x, y) => 0 <= x && x < r && 0 <= y && y < c;

// 다음에 탐색할 경로가 다음 단게에 물이 차는 위치인지 검사하는 함수
const willBeWatered = (r, c, forestBoard, fx, fy, tx, ty) => {
	for (let i = 0; i < 4; i++) {
		const [wx, wy] = [tx + cx[i], ty + cy[i]];

		if (!isPossibleRoute(r, c, wx, wy)) continue;
		if (wx === fx && wy === fy) continue;

		if (forestBoard[wx][wy] === "*") return true;
	}

	return false;
};

const BFS = (r, c, forestBoard, hedgehogQueue, waterQueue, times) => {
	// 다음 고슴도치 큐와 다음 물 큐
	let nextHedgehogQueue = new Queue();
	let nextWaterQueue = new Queue();

	while (!hedgehogQueue.isEmpty()) {
		// 우선 고슴도치 큐를 한 단계만큼 비워줍니다.
		while (!hedgehogQueue.isEmpty()) {
			const [fx, fy] = hedgehogQueue.dequeue();

			for (let i = 0; i < 4; i++) {
				const [tx, ty] = [fx + cx[i], fy + cy[i]];

				// 다음 경로가 티떱숲을 벗어난다면,
				if (!isPossibleRoute(r, c, tx, ty)) continue;
				// 다음 경로가 비버의 굴이라면,
				if (forestBoard[tx][ty] === "D") {
					times[tx][ty] = times[fx][fy] + 1;
					return;
				}

				// 다음 경로가 물이 범람할 위치라면,
				if (willBeWatered(r, c, forestBoard, fx, fy, tx, ty)) continue;
				// 다음 경로가 돌이거나 물이라면,
				if (forestBoard[tx][ty] === "X") continue;
				if (forestBoard[tx][ty] === "*") continue;
				// 다음 경로가 이미 탐색한 경로라면,
				if (times[tx][ty] !== -1) continue;

				// 시간 기록하고 다음 고슴도치 큐에 넣어주기
				times[tx][ty] = times[fx][fy] + 1;
				nextHedgehogQueue.enqueue([tx, ty]);
			}
		}

		// 물 큐도 한 단계 비워줍니다.
		while (!waterQueue.isEmpty()) {
			const [fx, fy] = waterQueue.dequeue();

			for (let i = 0; i < 4; i++) {
				const [tx, ty] = [fx + cx[i], fy + cy[i]];

				// 다음 경로가 티떱숲을 벗어난다면,
				if (!isPossibleRoute(r, c, tx, ty)) continue;
				// 다음 경로가 돌이거나 물이거나 비버의 굴이라면,
				if (forestBoard[tx][ty] === "X") continue;
				if (forestBoard[tx][ty] === "*") continue;
				if (forestBoard[tx][ty] === "D") continue;

				// 물 기록하고, 다음 물 큐에 넣어주기
				forestBoard[tx][ty] = "*";
				nextWaterQueue.enqueue([tx, ty]);
			}
		}

		// 다음 탐색을 위해서 큐를 이동시켜주기
		hedgehogQueue = nextHedgehogQueue;
		nextHedgehogQueue = new Queue();

		waterQueue = nextWaterQueue;
		nextWaterQueue = new Queue();
	}
};

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

	const times = Array.from({length: r}, () => Array(c).fill(-1));
	const hedgehogQueue = new Queue();
	const waterQueue = new Queue();

	// 고슴도치와 비버의 굴과 물의 위치 찾기
	let beaver = null;
	for (let i = 0; i < r; i++) {
		for (let j = 0; j < c; j++) {
			if (forestBoard[i][j] === "." || forestBoard[i][j] === "X") continue;

			if (forestBoard[i][j] === "S") {
				// 고슴도치 위치
				hedgehogQueue.enqueue([i, j]);
				forestBoard[i][j] = ".";
				times[i][j] = 0;
			} else if (forestBoard[i][j] === "*") {
				// 물의 위치
				waterQueue.enqueue([i, j]);
			} else if (forestBoard[i][j] === "D") {
				// 비버의 굴의 위치
				beaver = [i, j];
			}
		}
	}

	// BFS 탐색
	BFS(r, c, forestBoard, hedgehogQueue, waterQueue, times);

	// BFS 탐색을 종료해도, 비버의 굴에 도착하지 못한다면 "KAKTUS" 출력
	if (times[beaver[0]][beaver[1]] === -1) return "KAKTUS";
	// 비버의 굴까지의 시간 출력
	return times[beaver[0]][beaver[1]];
};

console.log(solution(input));