Node.js) 백준 9328번: 열쇠

https://www.acmicpc.net/problem/9328

9328번: 열쇠

 

class Node {
	constructor(item) {
		this.item = item;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.length = 0;
	}

	push(item) {
		const node = new Node(item);
		if (this.head == null) {
			this.head = node;
		} else {
			this.tail.next = node;
		}

		this.tail = node;
		this.length += 1;
	}

	pop() {
		const popItem = this.head;
		this.head = this.head.next;
		this.length -= 1;
		return popItem.item;
	}
}
const fs = require('fs');
const input = fs
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.trim());
const T = +input.shift();

const dx = [0, 0, 1, -1];
const dy = [-1, 1, 0, 0];

const isKey = (v) => v.charCodeAt(0) >= 97 && v.charCodeAt(0) <= 122;
const isDoor = (v) => v.charCodeAt(0) >= 65 && v.charCodeAt(0) <= 90;
const answer = [];
for (let i = 0; i < T; i++) {
	const [N, M] = input.shift().split(' ').map(Number);
	let board = [];
	let keys = new Set();
	let doors = new Map();
	let doc = 0;
	let path = new Queue();
	let visited = Array.from(Array(N), () => Array(M).fill(false));

	// 문찾기
	// 빌딩 만들기

	for (let r = 0; r < N; r++) {
		const line = input.shift().split('');
		if (r == 0 || r == N - 1) {
			line.forEach((v, c) => {
				if (v == '.') {
					path.push([r, c]);
				} else if (v == '$') {
					path.push([r, c]);
				} else if (isKey(v)) {
					keys.add(v);
					path.push([r, c]);
				} else if (isDoor(v)) {
					if (doors.has(v)) {
						const loc = doors.get(v);
						loc.push([r, c]);
						doors.set(v, loc);
					} else {
						doors.set(v, [[r, c]]);
					}
				}
			});
		} else {
			(line[0] + '*'.repeat(line.length - 2) + line[line.length - 1]).split('').forEach((v, c) => {
				if (v == '.') {
					path.push([r, c]);
				} else if (v == '$') {
					path.push([r, c]);
				} else if (isKey(v)) {
					keys.add(v);
					path.push([r, c]);
				} else if (isDoor(v)) {
					if (doors.has(v)) {
						const loc = doors.get(v);
						loc.push([r, c]);
						doors.set(v, loc);
					} else {
						doors.set(v, [[r, c]]);
					}
				}
			});
		}
		board.push(line);
	}
	input.shift()
		.split('')
		.forEach((v) => keys.add(v));

	// 여기까지 한게
	/**
	 * 빌딩 만들기 board
	 * 들어갈 수 있는 입구 찾기 path
	 * 빌딩 외곽에 있는 문 찾기 door
	 * 빌딩 외곽에 있는 열쇠 찾기 keys
	 */

	// console.log(board.map((v) => v.join('')).join('\n'));
	// console.log(keys.keys());
	// console.log(doors.entries());
	// console.log(path);

	/**
	 * 이제
	 * 1. 키로 딸 수 있는 곳 다 열기
	 * 2. 열고 거기 갈 수 있으니까 path에 추가하기
	 * 3. path로 돌아다니면서 문서 찾고 문이나 키 있으면 추가하기
	 *
	 */

	// 1. 키로 열 수 있는 곳 모두 열기
	// 2. 열고 거기 갈 수 있으면 path에 추가하기
	keys.forEach((key) => {
		const target = key.toUpperCase();
		if (doors.has(target)) {
			const loc = doors.get(target);
			loc.forEach((v) => {
				path.push(v);
			});
			doors.set(target, []);
		}
	});
	while (path.length > 0) {
		let cnt = path.length;
		while (cnt--) {
			const [x, y] = path.pop();
			if (visited[x][y]) continue;
			if (board[x][y] == '$') doc++;
			const q = new Queue();
			q.push([x, y]);
			visited[x][y] = true;
			while (q.length > 0) {
				const [cx, cy] = q.pop();
				for (let k = 0; k < 4; k++) {
					const nx = cx + dx[k];
					const ny = cy + dy[k];
					if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) continue;

					if (board[nx][ny] == '*') continue;
					else if (board[nx][ny] == '.') {
						q.push([nx, ny]);
						visited[nx][ny] = true;
					} else if (board[nx][ny] == '$') {
						doc++;
						board[nx][ny] = '.';
						q.push([nx, ny]);
						visited[nx][ny] = true;
					} else if (isKey(board[nx][ny])) {
						keys.add(board[nx][ny]);
						q.push([nx, ny]);
						visited[nx][ny] = true;
					} else if (isDoor(board[nx][ny])) {
						const DOOR = board[nx][ny];
						if (doors.has(DOOR)) {
							const loc = doors.get(DOOR);
							loc.push([nx, ny]);
							doors.set(DOOR, loc);
						} else {
							doors.set(DOOR, [[nx, ny]]);
						}
					}
				}
			}
		}

		keys.forEach((key) => {
			const target = key.toUpperCase();
			if (doors.has(target)) {
				const loc = doors.get(target);
				loc.forEach((v) => {
					path.push(v);
				});
				doors.set(target, []);
			}
		});
	}
	// console.log(doc);
	answer.push(doc);
}
console.log(answer.join('\n'));