TS) 백준 1385번: 벌집

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

1385번: 벌집

//https://www.acmicpc.net/problem/1385
// 벌집

const [S, E]: number[] = require('fs').readFileSync('./dev/stdin').toString().trim().split(' ').map(Number);
const honeycomb = Array.from(new Array(1000002), () => new Array(6).fill(0));

honeycomb[1] = [2, 0, 0, 0, 0, 0];
honeycomb[2] = [0, 0, 0, 1, 0, 0];

let dir = 2;
for (let i = 2; i <= 1000000; i++) {
	const lastjoin = honeycomb[i][(dir + 1) % 6];
	const front = honeycomb[lastjoin][(dir + 5) % 6];
	if (front == 0) {
		honeycomb[i][dir] = i + 1;
		honeycomb[i + 1][(dir + 3) % 6] = i;
		honeycomb[lastjoin][(dir + 5) % 6] = i + 1;
		honeycomb[i + 1][(dir + 2) % 6] = lastjoin;
	} else {
		honeycomb[i][dir] = front;
		honeycomb[front][(dir + 3) % 6] = i;
		honeycomb[i][(dir + 5) % 6] = i + 1;
		honeycomb[i + 1][(dir + 2) % 6] = i;
		honeycomb[front][(dir + 4) % 6] = i + 1;
		honeycomb[i + 1][(dir + 1) % 6] = front;
		dir -= 1;
	}
	dir = (dir + 1) % 6;
}

class Item {
	next?: Item;
	constructor(public value: any) {}
}

class Queue {
	head?: Item;
	tail?: Item;
	length: number;
	constructor() {
		this.length = 0;
	}

	push(item: any) {
		const node = new Item(item);
		if (this.head == null) {
			this.head = node;
		} else {
			if (this.tail) 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 ? popItem.value : null;
	}
}

const q = new Queue();
const prev = new Array(1000002).fill(-1);
q.push(S);
prev[S] = 0;
const answer = [];
while (q.length > 0) {
	const now = q.pop();

	if (now == E) {
		let path = now;
		while (path > 0) {
			answer.unshift(path);
			path = prev[path];
		}
		console.log(answer.join(' '));
		process.exit();
	}

	for (let i = 0; i < 6; i++) {
		const next = honeycomb[now][i];
		if (next == 0) continue;
		if (prev[next] == -1) {
			q.push(next);
			prev[next] = now;
		}
	}
}