[백준 13549] 숨바꼭질 3 (BFS/다익스트라, 자바스크립트)

숨바꼭질 3

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

풀이

1. BFS 풀이

덱을 이용한다.

아직 방문하지 않은 위치의 (x, 경과 시간)을 덱에 넣으며 탐색한다.

x가 k보다 크거나 같아지면 min(현재까지의 최단 시간, 경과 시간+x-k)로 최단 시간을 갱신한다.

x가 k보다 클 때도 답을 갱신하는 이유는 x가 k보다 커지면 뒤로 한 칸(x-1) 이동하는 경우만 남기 때문이다.

2. Dijkstra 풀이

우선순위 큐를 이용한다.

거리를 담은 배열 visited[nx]보다 거리가 작을 때만 우선순위 큐에 넣으며 탐색한다.

최단 시간일 경우만 큐에서 꺼내지므로 k에 도착하면 경과 시간을 출력하고 종료한다.

코드

BFS

class Node {
    constructor(x, sec) {
        this.x = x;
        this.sec = sec;
    }
}

class Deque {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    isEmpty() {
        if (this.length === 0) return true;
        else return false;
    }

    push(x, sec) {
        let node = new Node(x, sec);
        if (this.length === 0) this.head = node;
        else this.tail.next = node;
        this.tail = node;
        this.length++;
    }

    popleft() {
        let item = this.head;
        if (this.length === 0) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = this.head.next;
        }
        this.length--;
        return item;
    }
}

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, k] = require("fs").readFileSync(filePath).toString().trim().split(" ").map(Number);

let ans = Number.MAX_VALUE;

let queue = new Deque();
queue.push(n, 0);

let visited = Array(10001).fill(false);
visited[n] = true;

while (!queue.isEmpty()) {	// BFS 탐색
    let node = queue.popleft();
  	let [x, s] = [node.x, node.sec];
  
    if (s >= ans) continue;	// 경과 시간이 ans보다 커지면 넘어감
    if (x >= k) {	// x가 k보다 크거나 같아지면 ans 갱신
      	// x가 k보다 커지면 x-1로 이동하는 경우만 남기 때문에 더이상 덱에 넣지 않는다.
        ans = Math.min(ans, s+x-k);
        continue;
    }
  
  	for (let [nx, ns] of [[x*2, s], [x-1, s+1], [x+1, s+1]]) {	// 세 방향 탐색
      if (0 <= nx <= 100000 && !visited[nx]) {	// 범위 안에 있고 아직 방문하지 않은 위치여야 함
        visited[nx] = true;
        queue.push(nx, ns);
      }
    }
}

console.log(ans);

Dijkstra

class Node {
    constructor(x, sec) {
        this.x = x;
        this.sec = sec;
    }
}

// 우선순위 큐
class PriorityQueue {
    constructor() {
        this.heap = [ null ];
    }
    
    size() {
        return this.heap.length - 1;
    }
    
    swap(a, b) {
        [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
    }
    
    heappush(x, sec) {
        let data = new Node(x, sec);
        this.heap.push(data);
        let curIdx = this.heap.length - 1;
        let parIdx = (curIdx / 2) >> 0;
        
        while (curIdx > 1 && this.heap[parIdx].sec > this.heap[curIdx].sec) {
            this.swap(parIdx, curIdx)
            curIdx = parIdx;
            parIdx = (curIdx / 2) >> 0;
        }
    }
    
    heappop() {
        const min = this.heap[1];
        if (this.heap.length <= 2) this.heap = [ null ];
        else this.heap[1] = this.heap.pop();   
        
        let curIdx = 1;
        let leftIdx = curIdx * 2;
        let rightIdx = curIdx * 2 + 1; 
        
        if (!this.heap[leftIdx]) return min;
        if (!this.heap[rightIdx]) {
            if (this.heap[leftIdx].sec < this.heap[curIdx].sec) {
                this.swap(leftIdx, curIdx);
            }
            return min;
        }

        while (this.heap[leftIdx].sec < this.heap[curIdx].sec || this.heap[rightIdx].sec < this.heap[curIdx].sec) {
            const minIdx = this.heap[leftIdx].sec > this.heap[rightIdx].sec ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx * 2;
            rightIdx = curIdx * 2 + 1;
            if (leftIdx >= this.heap.length || rightIdx >= this.heap.length) break;
        }

        return min;
    }
}

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, k] = require("fs").readFileSync(filePath).toString().trim().split(" ").map(Number);

let queue = new PriorityQueue();
queue.heappush(n, 0);

let visited = Array(100001).fill(-1);
visited[n] = 0;

while (queue.size()) {	// Dijkstra 탐색
    let node = queue.heappop();
  	let [x, s] = [node.x, node.sec];
  
    if (x === k) {  // x가 k에 도달하면 종료
        console.log(s);
        break;
    }
  
  	for (let [nx, ns] of [[x*2, s], [x-1, s+1], [x+1, s+1]]) {	// 세 방향 탐색
      if (0 <= nx <= 100000 && (visited[nx] === -1 || visited[nx] > ns)) {	// 범위 안에 있고 현재보다 가중치가 작아야 함
        visited[nx] = ns;
        queue.heappush(nx, ns);
      }
    }
}