Node.js) 백준 16166번: 서울의 지하철

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

16166번: 서울의 지하철

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 input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));

const [N] = input.shift();
const [D] = input.pop();

const subway = {};

for (let i = 0; i < N; i++) {
	const line = input[i];
	const x = line.shift();
	for (let j = 0; j < x; j++) {
		if (subway[line[j]]) {
			subway[line[j]].push(i);
		} else {
			subway[line[j]] = [i];
		}
	}
}

let min = Infinity;
subway[0].forEach((v) => {
	const q = new Queue();

	let visited = new Set();

	q.push([0, 0, v]); //  현재 역, 환승횟수, 현재 호선
	visited.add(0);
	while (q.length > 0) {
		const [station, cnt, myline] = q.pop();

		if (station == D) {
			min = Math.min(min, cnt);
			break;
		}

		subway[station].forEach((line) => {
			const nowLine = input[line];
			for (let i = 0; i < nowLine.length; i++) {
				const st = nowLine[i];
				if (visited.has(st)) continue;
				visited.add(st);
				if (line != myline) {
					q.push([st, cnt + 1, line]);
				} else {
					q.push([st, cnt, line]);
				}
			}
		});
	}
});
console.log(min == Infinity ? -1 : min);