문제
접근법
처음에 단순 BFS로 풀려고 했으나, 이 문제에서는 간선의 비용이 모두 동일하지 않기 때문에 단순 BFS를 사용하면 안된다.
이 문제에서 간선의 비용은 움직일 때 걸리는 시간이다.
걸어서 이동할때는 1초, 텔레포트로 이동할 때는 0초가 간선의 비용이 된다.
0-1 BFS
간선의 가중치가 0또는 1이기 때문에 0-1 BFS로 풀면 최단 거리를 찾을 수 있다.
0-1 BFS란 간단히 정리해보자면 하나의 정점에서 인접한 정점으로 이동할 때, 가중치가 1이라면 거리가 더 멀어지는 것이므로 큐의 뒤에 삽입하고, 가중치가 0이라면 현재 거리를 그대로 유지하는 것이기 때문에 큐의 앞에 삽입하는 방식이다.
이로써 큐의 원소는 거리순으로 정렬된 상태를 유지한다.
더 자세한 설명은 아래 블로그에 잘 설명되어있다.
https://justicehui.github.io/medium-algorithm/2018/08/30/01BFS/
덱(Deque)을 사용하지 않은 0-1 BFS
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const visited = Array(10 ** 5 + 1).fill(false);
const queue = [[N, 0]];
let front = 0;
visited[N] = true;
let answer;
while (queue.length > front) {
const [cur, sec] = queue.shift();
if (cur === K) {
answer = sec;
break;
}
for (const next of [cur - 1, cur + 1, cur * 2]) {
if (!visited[next] && next >= 0 && next <= 100_000) {
if (next === cur * 2) {
queue.unshift([next, sec]);
} else {
queue.push([next, sec + 1]);
}
visited[next] = true;
}
}
}
console.log(answer);덱 자료구조를 사용하지 않고, 기본 내장 메서드인 shift()와 unshift()함수를 사용해줘도 통과할 수 있다. 하지만 해당 함수들은 원소를 삽입,삭제 하는데에 의 시간 복잡도를 가지기 때문에 동작 속도가 느리다는 단점이 있다.
덱(Deque)을 사용한 0-1 BFS
class Deque {
constructor() {
this.deque = {};
this.front = 0;
this.rear = 0;
}
pushFront(element) {
if (this.deque[this.front] === undefined) this.deque[this.front] = element;
else {
this.front--;
this.deque[this.front] = element;
}
}
popFront() {
const temp = this.deque[this.front];
delete this.deque[this.front];
this.front++;
if (this.front > this.rear) {
this.front = this.rear = 0;
}
return temp;
}
pushBack(element) {
if (this.deque[this.rear] === undefined) this.deque[this.rear] = element;
else {
this.rear++;
this.deque[this.rear] = element;
}
}
popBack() {
const temp = this.deque[this.rear];
delete this.deque[this.rear];
this.rear--;
if (this.front > this.rear) {
this.front = this.rear = 0;
}
return temp;
}
size() {
if (this.deque[this.front] === undefined) return 0;
return this.rear - this.front + 1;
}
}
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const visited = Array(10 ** 5 + 1).fill(false);
const deque = new Deque();
deque.pushBack([N, 0]);
visited[N] = true;
let answer;
while (deque.size() > 0) {
const [cur, sec] = deque.popFront();
if (cur === K) {
answer = sec;
break;
}
for (const next of [cur - 1, cur + 1, cur * 2]) {
if (!visited[next] && next >= 0 && next <= 100_000) {
if (next === cur * 2) {
deque.pushFront([next, sec]);
} else {
deque.pushBack([next, sec + 1]);
}
visited[next] = true;
}
}
}
console.log(answer);덱(Deque) 자료구조를 직접 구현해주면 원소를 앞과 뒤에서 전부 삽입,삭제 해줄 수 있고, 이때의 시간복잡도는 이다. 따라서 동작 속도가 훨씬 빨라진다.
다익스트라
오답(우선순위 큐 + BFS)
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const visited = Array(10 ** 5 + 1).fill(false);
class PriorityQueue {
constructor(time, cur) {
this.heap = [{ time, cur }];
}
enqueue(time, cur) {
this.heap.push({ time, cur });
this.heapifyUp(this.heap.length - 1);
}
dequeue() {
const min = this.heap[0];
const temp = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = temp;
this.heapifyDown(0);
}
return min;
}
heapifyUp(idx) {
while (idx > 0) {
let pIdx = (idx - 1) >> 1;
if (this.heap[idx].time < this.heap[pIdx].time) {
[this.heap[idx], this.heap[pIdx]] = [this.heap[pIdx], this.heap[idx]];
} else break;
pIdx = idx;
}
}
heapifyDown(idx) {
while (idx < this.heap.length - 1) {
let lcIdx = (idx << 1) + 1;
let rcIdx = (idx << 1) + 2;
let smaller = idx;
if (this.heap[lcIdx] && this.heap[lcIdx].time < this.heap[smaller].time) smaller = lcIdx;
if (this.heap[rcIdx] && this.heap[rcIdx].time < this.heap[smaller].time) smaller = rcIdx;
if (smaller === idx) break;
[this.heap[smaller], this.heap[idx]] = [this.heap[idx], this.heap[smaller]];
idx = smaller;
}
}
size() {
return this.heap.length;
}
}
const pq = new PriorityQueue(0, N);
visited[N] = true;
while (pq.size() > 0) {
const { time, cur } = pq.dequeue();
if (cur === K) {
answer = time;
break;
}
for (const next of [cur + 1, cur - 1, cur * 2]) {
if (!visited[next] && next >= 0 && next <= 100000) {
if (next === cur * 2) {
pq.enqueue(time, next);
} else {
pq.enqueue(time + 1, next);
}
visited[next] = true;
}
}
}
console.log(answer);위 코드는 다익스트라는 아니고 우선순위 큐와 BFS를 결합한 방식이다.
0-1 BFS에서는 가중치에 따라 원소를 앞 혹은 뒤에 삽입해줌으로써 큐의 원소를 정렬된 상태로 유지해줬었다.
큐의 원소를 정렬된 상태로 유지하는 것이 핵심이라면 우선순위 큐를 사용해도된다.
하지만 위 코드는 오답이다.
왜일까?
입력이 4 6 이 들어오고, 4+1, 4-1을 수행해서 큐에 5와 3이 들어있다고 가정해보자.
4 -> 5 -> 6 순서로 이동하면 총 2초의 시간이 걸리지만, 4 -> 3 -> 6 순서로 이동하면 총 1초의 시간으로 최단 시간이다.
그러나 큐에서 5가 먼저 나올 경우 5+1이 먼저 수행되어서 6을 방문하고 큐에 넣을 것이다. 그리고 큐에서 3이 나왔는데 *2로 6을 방문하려고 보니 6이 이미 방문한 곳이라 방문하지 못하므로 답은 2초가 된다.
for문에서 [cur + 1, cur - 1, cur * 2] 를 [cur - 1, cur + 1, cur * 2] 로 순서를 바꾸어준다면 위 반례에서는 답을 찾을 수 있겠지만 다른 반례들이 더 존재할 것이다.
이미 방문한 적 있는 정점은 다시 방문하지 않는다는 BFS의 특징때문에 첫 방문시 정답이 결정되며, 최단거리가 갱신될 수 있는 상황이 오더라도 정점을 재방문하지 않기 때문에 정답이 갱신되지 않는다.
정답 (우선순위 큐 + 다익스트라)
visited 로 방문체크를 하는 대신 distance배열을 만들어서 최단거리를 갱신할 수 있을 경우 갱신해주도록 했다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const distance = Array(10 ** 5 + 1).fill(Infinity);
class PriorityQueue {
constructor(time, cur) {
this.heap = [{ time, cur }];
}
enqueue(time, cur) {
this.heap.push({ time, cur });
this.heapifyUp(this.heap.length - 1);
}
dequeue() {
const min = this.heap[0];
const temp = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = temp;
this.heapifyDown(0);
}
return min;
}
heapifyUp(idx) {
while (idx > 0) {
let pIdx = (idx - 1) >> 1;
if (this.heap[idx].time < this.heap[pIdx].time) {
[this.heap[idx], this.heap[pIdx]] = [this.heap[pIdx], this.heap[idx]];
} else break;
idx = pIdx;
}
}
heapifyDown(idx) {
while (idx < this.heap.length - 1) {
let lcIdx = (idx << 1) + 1;
let rcIdx = (idx << 1) + 2;
let smaller = idx;
if (this.heap[lcIdx] && this.heap[lcIdx].time < this.heap[smaller].time) smaller = lcIdx;
if (this.heap[rcIdx] && this.heap[rcIdx].time < this.heap[smaller].time) smaller = rcIdx;
if (smaller === idx) break;
[this.heap[smaller], this.heap[idx]] = [this.heap[idx], this.heap[smaller]];
idx = smaller;
}
}
size() {
return this.heap.length;
}
}
const pq = new PriorityQueue(0, N);
distance[N] = 0;
while (pq.size() > 0) {
const { time, cur } = pq.dequeue();
for (const next of [cur - 1, cur + 1, cur * 2]) {
let cost;
if (next === cur * 2) cost = 0;
else cost = 1;
if (distance[next] > distance[cur] + cost) {
distance[next] = distance[cur] + cost;
pq.enqueue(time + cost, next);
}
}
}
console.log(distance[K]);우선순위 큐는 원소를 삽입,삭제할 때마다 의 시간이 걸리기 때문에 덱(Deque)을 사용했을 때보다 속도는 느리다.
BFS
*2를 별도의 간선으로 생각하지 않고, +1이나 -1를 적용한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법을 사용하면 별도의 자료구조를 사용하지 않아도 풀 수 있다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const visited = Array(10 ** 5 + 1).fill(false);
const queue = [[0, N]];
visited[N] = true;
double(0, N * 2);
let front = 0;
let answer;
while (queue.length > front) {
const [time, cur] = queue[front++];
if (cur === K) {
answer = time;
break;
}
for (const next of [cur - 1, cur + 1]) {
if (!visited[next] && next >= 0 && next <= 100000) {
queue.push([time + 1, next]);
visited[next] = true;
double(time + 1, next * 2);
}
}
}
function double(time, cur) {
if (cur > 100000 || visited[cur] || cur === 0) return;
double(time, cur * 2);
queue.push([time, cur]);
visited[cur] = true;
}
console.log(answer);double()함수의 종료조건은 cur이 100000을 넘었을 때, cur이 이미 방문한 적 있는 곳일 때, cur이 0일때가 있다.
cur이 0일 때는 0*2 = 0이라서 무한루프를 돌기 때문에 종료조건으로 설정해주고 cur이 이미 이전에 방문한 적 있는 곳일 때는 cur의 2의 거듭제곱 배인 좌표들도 모두 방문한 적 있는 곳일 것이기 때문에 바로 종료해줘서 수행시간을 단축시킨다.
