티스토리 뷰
https://www.acmicpc.net/problem/16166
16166번: 서울의 지하철
서울의 지하철 노선은 총 3개이다. 1호선에는 0, 2, 3번 역이 있고, 2호선에는 2, 5, 7, 10번 역이 있고, 3호선에는 10, 8번 역이 있다. 출발역인 0번 역에서 8번 역으로 가는 최소 환승 회수는 (호선, 역)
www.acmicpc.net
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);
728x90
'자료구조 알고리즘 > 백준' 카테고리의 다른 글
Node.js) 백준 27896번: 특별한 서빙 (0) | 2023.09.28 |
---|---|
Node.js) 백준 10813번: 공 바꾸기 (0) | 2023.09.28 |
Node.js) 백준 5597번: 과제 안 내신 분..? (0) | 2023.09.26 |
Node.js) 백준 2420번: 사파리 월드 (0) | 2023.09.25 |
Text) 백준 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1 (0) | 2023.09.24 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 개발자면접
- create db
- BFS
- 다이나밍프로그래밍
- 서버개발
- 최소공통조상
- 다이나믹프로그래밍
- 은둔청년체험
- MySQL
- 투포인터 연습
- 면접비
- 롱베케이션
- DB 생성
- 투포인터
- node.js
- MOD
- 동적프로그래밍
- 로드나인
- 그래프
- create databases;
- KMP
- 서버점검
- 면접질문
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
글 보관함