티스토리 뷰
https://www.acmicpc.net/problem/1385
1385번: 벌집
첫째 줄에는 당신이 있는 방의 번호 a와 출구가 있는 방의 번호 b가 주어진다.1 ≤ a, b ≤ 1,000,000)
www.acmicpc.net
//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;
}
}
}
728x90
'자료구조 알고리즘 > 백준' 카테고리의 다른 글
TS) 백준 7662번: 이중 우선순위 큐 (0) | 2024.03.01 |
---|---|
TS) 백준 15806번: 영우의 기숙사 청소 (1) | 2024.02.29 |
TS)백준 6588번: 골드바흐의 추측 (0) | 2024.02.28 |
Node.js) 백준 14245번: XOR (1) | 2024.02.28 |
Node.js) 백준 1395번: 스위치 (0) | 2024.02.28 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 투포인터
- 면접비
- 개발자면접
- 최소공통조상
- DB 생성
- create db
- MOD
- 은둔청년체험
- MySQL
- 동적프로그래밍
- 투포인터 연습
- 면접질문
- 그래프
- 롱베케이션
- node.js
- 다이나밍프로그래밍
- 다이나믹프로그래밍
- 로드나인
- create databases;
- BFS
- 서버점검
- 서버개발
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함