[백준] 22865 가장 먼 곳 (Javascript)

문제

BOJ22865_가장 먼 곳

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const [A, B, C] = input[1].split(' ').map(Number);
const M = +input[2];
const road = input.slice(3).map((e) => e.split(' ').map(Number));
const graph = Array.from({ length: N + 1 }, () => []);
road.forEach(([s, e, v]) => {
    graph[s].push([e, v]);
    graph[e].push([s, v]);
});

class PriorityQueue {
    constructor() {
        this.heap = [];
    }

    enqueue(node, priority) {
        this.heap.push({ node, priority });
        this.heapifyUp(this.heap.length - 1);
    }

    heapifyUp(index) {
        while (index > 0) {
            const parentIndex = (index - 1) >> 1;
            if (this.heap[parentIndex].priority <= this.heap[index].priority) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    dequeue() {
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.heapifyDown(0);
        }
        return min;
    }

    heapifyDown(index) {
        while (index < this.heap.length) {
            const left = (index << 1) + 1;
            const right = (index << 1) + 2;
            let smallest = index;
            if (left < this.heap.length && this.heap[left].priority < this.heap[smallest].priority) {
                smallest = left;
            }
            if (right < this.heap.length && this.heap[right].priority < this.heap[smallest].priority) {
                smallest = right;
            }
            if (smallest === index) break;
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            index = smallest;
        }
    }

    isEmpty() {
        return this.heap.length === 0;
    }
}

function dijkstra(start) {
    const distance = Array(N + 1).fill(INF);
    distance[start] = 0;
    const pq = new PriorityQueue();
    pq.enqueue(start, 0);
    while (!pq.isEmpty()) {
        const { node, priority } = pq.dequeue();
        if (priority > distance[node]) continue;
        for (let [v, d] of graph[node]) {
            const cost = priority + d;
            if (cost < distance[v]) {
                distance[v] = cost;
                pq.enqueue(v, cost);
            }
        }
    }
    return distance;
}

const INF = Infinity;

const distA = dijkstra(A);
const distB = dijkstra(B);
const distC = dijkstra(C);

let furthest = 0;
let answer = 0;

for (let i = 1; i <= N; i++) {
    const minDist = Math.min(distA[i], distB[i], distC[i]);
    if (furthest < minDist) {
        furthest = minDist;
        answer = i;
    }
}

console.log(answer);

시간 복잡도

이 문제는 다익스트라 알고리즘을 사용해서 풀 수 있는 문제다.
다익스트라 알고리즘을 구현하는 방법은 두 가지가 존재한다.

1. 우선순위 큐를 사용하지 않은 방식
2. 우선순위 큐를 사용한 방식

1번은 구현은 간단하지만 동작 속도가 느리다는 특징이 있고, 2번은 반대로 구현은 조금 복잡하지만 동작이 더 빠르다.

(V: 정점의 개수, E: 간선의 개수) 일때,
1번은 $O(V^2)$ 의 시간복잡도를 갖고, 2번은 $O(ElogV)$ 의 시간복잡도를 갖는다.

이 문제에서 V는 땅의 개수를 말하고, E는 땅과 땅을 잇는 도로를 말한다. $1\le V\le 100,000$ 이고, $V-1 \le E \le 500,000$ 이므로 1번 방식으로 풀면 O(10$^1$$^2$) 라서 시간 초과가 발생하므로 2번 방식으로 풀어야 한다.

풀이

우선 각 정점과 간선의 정보를 입력받아 입력값을 기반으로 그래프를 만든다.

const road = input.slice(3).map((e) => e.split(' ').map(Number));
const graph = Array.from({ length: N + 1 }, () => []);
// s=출발점, e=도착점, v=거리
road.forEach(([s, e, v]) => {
    graph[s].push([e, v]);
    graph[e].push([s, v]);
});

그리고 자바스크립트는 우선순위 큐를 지원하는 내장 모듈이 없기 때문에 다익스트라 알고리즘에 사용할 우선순위 큐를 직접 구현해준다.

class PriorityQueue {
    // 생성자
    constructor() {
        this.heap = [];
    }
  
	// 데이터 추가
    enqueue(node, priority) {
        this.heap.push({ node, priority });
        this.heapifyUp(this.heap.length - 1);
    }
	// 추가한 노드를 최소힙의 규칙에 맞게 위로 올려가며 배치한다.
    heapifyUp(index) {
        while (index > 0) {
            const parentIndex = (index - 1) >> 1;
            if (this.heap[parentIndex].priority <= this.heap[index].priority) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }
	
    // 데이터 삭제
    dequeue() {
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.heapifyDown(0);
        }
        return min;
    }
	// 루트노드가 삭제되었으므로 제일 마지막 노드를 루트노드에 삽입해서 최소힙의 규칙에 맞게 아래로 내려가며 배치한다.
    heapifyDown(index) {
        while (index < this.heap.length) {
            const left = (index << 1) + 1;
            const right = (index << 1) + 2;
            let smallest = index;
            if (left < this.heap.length && this.heap[left].priority < this.heap[smallest].priority) {
                smallest = left;
            }
            if (right < this.heap.length && this.heap[right].priority < this.heap[smallest].priority) {
                smallest = right;
            }
            if (smallest === index) break;
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            index = smallest;
        }
    }
	// 힙이 비었는지 확인한다.
    isEmpty() {
        return this.heap.length === 0;
    }
}

그리고 다익스트라 알고리즘을 구현해준다.

function dijkstra(start) {
    const distance = Array(N + 1).fill(INF);
    distance[start] = 0;
    const pq = new PriorityQueue();
    pq.enqueue(start, 0);
    while (!pq.isEmpty()) {
        const { node, priority } = pq.dequeue();
        if (priority > distance[node]) continue;
        for (let [v, d] of graph[node]) {
            const cost = priority + d;
            if (cost < distance[v]) {
                distance[v] = cost;
                pq.enqueue(v, cost);
            }
        }
    }
    return distance;
}

시작점으로부터 각 노드까지의 최단 거리를 저장할 배열을 만들고,

const distance = Array(N + 1).fill(INF);

시작 노드로 부터 시작 노드까지의 거리는 0이기 때문에 시작 노드의 거리는 0으로 초기화 한다.

distance[start] = 0;

우선순위 큐를 만들어주고, (시작노드, 거리)를 큐에 삽입한다.

const pq = new PriorityQueue();
pq.enqueue(start, 0);

큐에 루트노드에는 항상 거리(비용)이 최소인 노드가 저장된다.

큐가 빌 때까지 반복문을 수행해주며, 비용이 제일 작은 노드를 큐에서 뽑아서 최단거리를 갱신해줄 수 있으면 갱신하고, 갱신할 수 없으면 그냥 다음 반복문으로 넘어간다.

while (!pq.isEmpty()) {
    const { node, priority } = pq.dequeue();
    if (priority > distance[node]) continue;
    for (let [v, d] of graph[node]) {
      const cost = priority + d;
      if (cost < distance[v]) {
        distance[v] = cost;
        pq.enqueue(v, cost);
      }
    }
  }

반복문이 종료되면 시작점으로부터 각 노드까지의 최단 거리가 저장된 배열을 반환한다.

return distance;

그리고 A,B,C 의 위치에서 다익스트라 함수를 실행시켜주고,

const distA = dijkstra(A);
const distB = dijkstra(B);
const distC = dijkstra(C);

문제에서 가장 먼 곳은 선택할 집에서 거리가 가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 의미한다고 하였으므로 아래와 같이 코드를 작성해준다.

const distA = dijkstra(A);
const distB = dijkstra(B);
const distC = dijkstra(C);

let furthest = 0;
let answer = 0;

for (let i = 1; i <= N; i++) {
    // 가장 가까운 친구의 거리
    const minDist = Math.min(distA[i], distB[i], distC[i]);
    // 가장 가까운 친구의 거리를 기준으로 가장 먼 곳
    if (furthest < minDist) {
        furthest = minDist;
        answer = i;
    }
}

console.log(answer);