5719 거의 최단 경로 (자바스크립트)

문제

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

=====

문제 풀이

우선 다익스트라 방식으로 출발 지점부터 도착 지점까지의 최단 경로를 구한 뒤 그 방식으로 이동했을 경우 지나쳤던 경로들을 false 처리 해주고 false 경로는 패스하면서 다시 한번 다익스트라 방식으로 최단 거리를 찾으면 된다. 

처음 다익스트라 방식으로 경로를 탐색할 때 특정 지점까지 동일한 이동거리로 오는 경우가 있을 수 있다. 기록 된 distances[next] 와 값이 같다고 해서 그것 또한 힙에 넣어주면 시간 초과가 발생할 것 같았다. 때문에 distances의 각 노드에는 가중치를 뜻하는 weight과 거기 까지 온 이전 노드의 값을 기록해줄 previous를 Set으로 지정해줬다. 특정 지점까지 이동했을 때 더 작은 가중치로 갱신 됐다면 previous는 clear로 이전 기록을 치우고 지금의 이전 노드를 추가해주면 된다. 만약 기록된 weight 과 동일한 가중치로 방문했다면 previous에 기록만 해주고 힙에는 추가 안해주면 된다.

아래는 힙 구현 부분

class Heap {
    heapq;
    constructor() {
        this.heapq = [undefined];
    }
    isEmpty() {
        return this.heapq.length === 1;
    }
    swap(src, des) {
        [this.heapq[src], this.heapq[des]] = [this.heapq[des], this.heapq[src]];
    }
    push(arr) {
        this.heapq.push(arr);
        let cur = this.heapq.length - 1;
        while (cur > 1) {
            let parent = Math.floor(cur / 2);
            if (this.heapq[parent][0] > this.heapq[cur][0]) {
                this.swap(cur, parent);
                cur = parent;
            } else {
                break;
            }
        }
    }
    pop() {
        if (this.isEmpty()) return undefined;
        const root = this.heapq[1];
        const last = this.heapq.pop();
        if (this.isEmpty()) return last;
        this.heapq[1] = last;
        let cur = 1;
        while (cur * 2 < this.heapq.length) {
            let smallest = cur * 2;

            const right = cur * 2 + 1;
            if (
                right < this.heapq.length &&
                this.heapq[smallest][0] > this.heapq[right][0]
            ) {
                smallest = right;
            }

            if (this.heapq[cur][0] > this.heapq[smallest][0]) {
                this.swap(cur, smallest);
                cur = smallest;
            } else {
                break;
            }
        }
        return root;
    }
}

입력값을 받아올 재량으로 만든 함수

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const LEN = input.length;

let idx = 0;
const init = () => {
    const [n, m] = input[idx++].split(' ').map(Number);
    const [s, e] = input[idx++].split(' ').map(Number);
    const arr = input.slice(idx, idx + m).map((s) => s.split(' ').map(Number));
    idx += m;
    return {
        n,
        m,
        s,
        e,
        arr,
    };
};

아래는 위에서 설명한 로직을 코드로 구현한 부분이다.

도착 지점까지 동일한 최단 거리로 여러 경로가 있더라도 그 최단 거리 이전에 처리 됐으므로 cur이 도착지점과 같다면 반복문을 종료해줘도 무방하다.

const { n, m, s, e, arr } = init();
const gr = Array.from({ length: n }, () => []);
for (const [s, e, v] of arr) {
    gr[s].push([e, v]);
}
const distances = Array.from({ length: n }, () => ({
    weight: Infinity,
    previousNode: new Set(),
}));
	// 거의 최단 경로를 구할 때 방문하면 안되는 경로를 피하기 위해 선언된 배열
const routes = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => true)
);
const hq = new Heap();
distances[s].previousNode.add(-1);
distances[s].weight = 0;
hq.push([0, s]);

while (!hq.isEmpty()) {
    const [totalDistance, cur] = hq.pop();
    if (cur !== e && totalDistance > distances[e]) {
        break;
    }
    if (cur === e) {
        break;
    }
    for (const [next, value] of gr[cur]) {
        const nextDis = totalDistance + value;
        	// 동일 가중치라면 방문 경로에 추가
        if (distances[next].weight === nextDis) {
            distances[next].previousNode.add(cur);
            continue;
        }
        if (distances[next].weight < nextDis) continue;
        distances[next].weight = nextDis;
        distances[next].previousNode.clear();	// 갱신되는 더 작은 가중치라면 이전 방문 치우고 새로이 기록
        distances[next].previousNode.add(cur);
        hq.push([nextDis, next]);
    }
}

이제 거의 최단 경로를 구하기 위해 방문해서는 안되는 경로들을 기록하는 로직을 시작한다.

이는 도착지점부터 시작하여 previous들을 방문하면서 출발 지점까지 반복문을 돌린다.

const q = [e];
const visited = Array.from({ length: n }, () => false);
while (q.length) {
    const cur = q.shift();
    if (cur === s) continue;
    for (const p of distances[cur].previousNode) {
        routes[p][cur] = false;
        if (visited[p]) continue;	// 동일한 지점을 또 방문할 필요 없으니 처리
        visited[p] = true;
        q.push(p);
    }
}

이제 위에서 구한 routes 경로들은 피하면서 최단 경로를 구하면 된다.

const a = new Heap();
a.push([0, s]);

const dd = Array.from({ length: n }, () => Infinity);
dd[s] = 0;
while (!a.isEmpty()) {
    const [total, cur] = a.pop();
    if (cur === e) break;
    for (const [next, v] of gr[cur]) {
        const nv = v + total;
        if (routes[cur][next] === false) continue;
        if (dd[next] <= nv) continue;

        dd[next] = nv;
        a.push([nv, next]);
    }
}

if (dd[e] === Infinity) {
    answers.push(-1);
} else {
    answers.push(dd[e]);
}

정답 코드

class Heap {
    heapq;
    constructor() {
        this.heapq = [undefined];
    }
    isEmpty() {
        return this.heapq.length === 1;
    }
    swap(src, des) {
        [this.heapq[src], this.heapq[des]] = [this.heapq[des], this.heapq[src]];
    }
    push(arr) {
        this.heapq.push(arr);
        let cur = this.heapq.length - 1;
        while (cur > 1) {
            let parent = Math.floor(cur / 2);
            if (this.heapq[parent][0] > this.heapq[cur][0]) {
                this.swap(cur, parent);
                cur = parent;
            } else {
                break;
            }
        }
    }
    pop() {
        if (this.isEmpty()) return undefined;
        const root = this.heapq[1];
        const last = this.heapq.pop();
        if (this.isEmpty()) return last;
        this.heapq[1] = last;
        let cur = 1;
        while (cur * 2 < this.heapq.length) {
            let smallest = cur * 2;

            const right = cur * 2 + 1;
            if (
                right < this.heapq.length &&
                this.heapq[smallest][0] > this.heapq[right][0]
            ) {
                smallest = right;
            }

            if (this.heapq[cur][0] > this.heapq[smallest][0]) {
                this.swap(cur, smallest);
                cur = smallest;
            } else {
                break;
            }
        }
        return root;
    }
}

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const LEN = input.length;

let idx = 0;
const init = () => {
    const [n, m] = input[idx++].split(' ').map(Number);
    const [s, e] = input[idx++].split(' ').map(Number);
    const arr = input.slice(idx, idx + m).map((s) => s.split(' ').map(Number));
    idx += m;
    return {
        n,
        m,
        s,
        e,
        arr,
    };
};
const answers = [];
while (idx < LEN - 1) {
const { n, m, s, e, arr } = init();
const gr = Array.from({ length: n }, () => []);
for (const [s, e, v] of arr) {
    gr[s].push([e, v]);
}
const distances = Array.from({ length: n }, () => ({
    weight: Infinity,
    previousNode: new Set(),
}));
const routes = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => true)
);
const hq = new Heap();
distances[s].previousNode.add(-1);
distances[s].weight = 0;
hq.push([0, s]);

while (!hq.isEmpty()) {
    const [totalDistance, cur] = hq.pop();
    if (cur !== e && totalDistance > distances[e]) {
        break;
    }
    if (cur === e) {
        break;
    }
    for (const [next, value] of gr[cur]) {
        const nextDis = totalDistance + value;
        if (distances[next].weight === nextDis) {
            distances[next].previousNode.add(cur);
            continue;
        }
        if (distances[next].weight < nextDis) continue;
        distances[next].weight = nextDis;
        distances[next].previousNode.clear();
        distances[next].previousNode.add(cur);
        hq.push([nextDis, next]);
    }
}

const q = [e];
const visited = Array.from({ length: n }, () => false);
while (q.length) {
    const cur = q.shift();
    if (cur === s) continue;
    for (const p of distances[cur].previousNode) {
        routes[p][cur] = false;
        if (visited[p]) continue;
        visited[p] = true;
        q.push(p);
    }
}

const a = new Heap();
a.push([0, s]);

const dd = Array.from({ length: n }, () => Infinity);
dd[s] = 0;
while (!a.isEmpty()) {
    const [total, cur] = a.pop();
    if (cur === e) break;
    for (const [next, v] of gr[cur]) {
        const nv = v + total;
        if (routes[cur][next] === false) continue;
        if (dd[next] <= nv) continue;

        dd[next] = nv;
        a.push([nv, next]);
    }
}

if (dd[e] === Infinity) {
    answers.push(-1);
} else {
    answers.push(dd[e]);
}
}

console.log(answers.join('\n'));