[백준] 1238_파티 (Javascript)

문제

BOJ1238_파티

풀이

요구사항

1번부터 N번까지의 마을이 있고, 마을 사이는 단방향 도로로 이어져있다.

X번 마을에서 파티가 열릴 때,각 마을에서 X번 마을까지 갔다가 다시 돌아오는 거리가 가장 먼 마을의 거리를 출력하라.

도로가 단방향이기 때문에 갈 때랑 올 때 거쳐가는 도로가 다를 수 있다.

이동할 때는 최단 거리로 이동한다.

해결방안

다익스트라 알고리즘을 사용해서 모든 노드에서 X노드로 가는 최단 거리를 구한 뒤, X노드에서 모든 노드까지 가는 최단 거리를 더하면 모든 마을에서 X마을까지 왔다 갔다 했을때의 최단 거리를 구할 수 있다.

그리고 최단거리의 값이 가장 큰 값을 출력하면 가장 먼 거리를 구할 수 있다.

시간초과

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, X] = input[0].split(' ').map(Number);
const arr = input.slice(1, 1 + M).map((e) => e.split(' ').map(Number));
const graph = Array.from({ length: N + 1 }, () => []);
const distance = Array(N + 1).fill(Infinity);
const dists = Array(N + 1).fill(0);

for (const [s, e, t] of arr) {
    graph[s].push([e, t]);
}

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

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

    heepifyUp(idx) {
        while (idx > 0) {
            const parent = (idx - 1) >> 1;
            if (this.heap[parent].priority > this.heap[idx].priority) {
                [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
            } else break;
            idx = parent;
        }
    }

    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;
    }
    heapifyDown(idx) {
        while (idx < this.heap.length) {
            const lc = (idx << 1) + 1;
            const rc = (idx << 1) + 2;
            let smaller = idx;
            if (this.heap[lc] && this.heap[lc].priority > this.heap[smaller].priority) {
                smaller = lc;
            }
            if (this.heap[rc] && this.heap[rc].priority > this.heap[smaller].priority) {
                smaller = rc;
            }
            if (idx === smaller) break;
            [this.heap[idx], this.heap[smaller]] = [this.heap[smaller], this.heap[idx]];
            idx = smaller;
        }
    }
    isEmpty() {
        return this.heap.length === 0;
    }
}

function dijkstra(start) {
    const pq = new PriorityQueue();
    distance[start] = 0;
    pq.enqueue(start, 0);

    while (!pq.isEmpty()) {
        const { node, priority } = pq.dequeue();
        if (distance[node] < priority) continue;
        for (const [next, cost] of graph[node]) {
            // 최단거리 갱신
            if (distance[next] > distance[node] + cost) {
                distance[next] = distance[node] + cost;
                pq.enqueue(next, distance[next]);
            }
        }
    }

    if (start === X) {
        for (let i = 1; i < distance.length; i++) {
            dists[i] += distance[i];
        }
    }

    return distance[X];
}

for (let i = 1; i <= N; i++) {
    dists[i] += dijkstra(i);
    distance.fill(Infinity);
}

console.log(Math.max(...dists));

위와 같이 작성할 경우 다익스트라 알고리즘을 N번 수행한다.
이럴 경우 시간복잡도는 $O(N * (M \log N))$이고, 이는 $1,000 * 100,000$ 번의 연산을 수행하기 때문에 시간 초과가 발생한다.

X노드에서 다른 노드로 이동하는 최단 거리는 X를 출발 노드로 지정해서 다익스트라 알고리즘을 한 번만 수행하면 구할 수 있지만, 다른 노드에서 X번 노드로 가는 최단거리를 구하기 위해서는 각각의 노드를 출발 노드로 지정해줘야 하기 때문에 다익스트라 알고리즘을 N(노드의 개수)번 수행해줘야한다.

이를 그래프를 만들 때, 역방향 그래프도 만들어줌으로써 해결할 수 있다.

통과

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, X] = input[0].split(' ').map(Number);
const arr = input.slice(1, 1 + M).map((e) => e.split(' ').map(Number));
const graph = Array.from({ length: N + 1 }, () => []);
const reverseGraph = Array.from({ length: N + 1 }, () => []);
const distance1 = Array(N + 1).fill(Infinity);
const distance2 = Array(N + 1).fill(Infinity);
let answer = 0;

arr.forEach(([s, e, t]) => {
    graph[s].push([e, t]);
    reverseGraph[e].push([s, t]);
});

class PriorityQueue {
    constructor() {
        this.heap = [];
    }
    enqueue(priority, node) {
        this.heap.push({ priority, node });
        this.heapifyUp(this.heap.length - 1);
    }
    heapifyUp(idx) {
        while (idx > 0) {
            const pIdx = (idx - 1) >> 1;
            if (this.heap[pIdx].priority > this.heap[idx].priority) {
                [this.heap[pIdx], this.heap[idx]] = [this.heap[idx], this.heap[pIdx]];
            } else break;
            idx = pIdx;
        }
    }
    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;
    }
    heapifyDown(idx) {
        while (idx < this.heap.length - 1) {
            const lcIdx = idx * 2 + 1;
            const rcIdx = idx * 2 + 2;
            let smaller = idx;
            if (this.heap[lcIdx] && this.heap[lcIdx].priority < this.heap[idx].priority) smaller = lcIdx;
            if (this.heap[rcIdx] && this.heap[rcIdx].priority < this.heap[idx].priority) 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;
    }
}

function dijkstra(start, graph, distance) {
    const pq = new PriorityQueue();
    pq.enqueue(0, start);
    distance[start] = 0;

    while (pq.size() > 0) {
        const { priority, node } = pq.dequeue();
        if (distance[node] < priority) continue;
        for (const [next, time] of graph[node]) {
            const cost = distance[node] + time;
            if (distance[next] > cost) {
                distance[next] = cost;
                pq.enqueue(cost, next);
            }
        }
    }
}

dijkstra(X, graph, distance1);
dijkstra(X, reverseGraph, distance2);

for (let i = 1; i <= N; i++) {
    const dist = distance1[i] + distance2[i];
    answer = Math.max(answer, dist);
}

console.log(answer);

한 번은 정방향 그래프를 이용해서 X로부터 모든 노드까지의 최단 거리를 구한다. 이는 X마을에서 모든 마을까지 돌아갈 때의 최단 거리이다.

다른 한 번은 역방향 그래프를 이용해서 X로부터 모든 노드까지의 최단 거리를 구한다. 이는 모든 마을에서 X마을까지 이동할 때의 최단 거리이다.

이로써 다익스트라 알고리즘을 총 두 번만 사용해서 정답을 구할 수 있기 때문에 시간초과 없이 답을 출력할 수 있다.