22870 산책 (자바스크립트)

문제

코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다.

현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 $E$에서 $S$로 올 때 $S$에서 $E$로 가는 도중에 방문한 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 $S$에서 $E$로 가는 가장 짧은 거리와 $E$에서 $S$로 가는 가장 짧은 거리를 원한다.

정점 $S$에서 정점 $E$로 이동할 때, 가장 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 $S$에서 정점 $E$로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 가장 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정을 해보자. 두 개의 경로중 사전순으로 먼저 오는 것은 1 3 4 2이므로 정점 1에서 정점 2로 가는 최단 경로 중 두 번째 것을 선택한다.

이와 같이 산책 경로를 정할 때, 산책 전체 경로의 거리($S$에서 $E$로 가는 거리 + $E$에서 $S$로 가는 거리)를 구해보자.

=====

문제 풀이 

s부터 e 까지 가는 최단 경로를 찾은 뒤 그 최단 경로에서 방문한 정점은 제외한 채 e부터 s로 이동하면 되는 문제이다.

이 때 s부터 e로 갈 때에는 같은 가중치라면 사전 순으로 앞에 있는 경로를 선택해야 한다는 점을 유의 해야한다.

이것을 위해 각 정점에 대해 움직임 가중치와 거기까지 도달하는 경로를 기록해줄 것이다. 

const distances = Array.from({ length: n + 1 }, () => ({
    weight: Infinity,
    path: ``,
}));

 

정점을 방문했는데 움직임 가중치가 기록된 것과 같다면  distances[next].path 와 curPath 를 localCompare 해줘서 -1 이라면 기존 경로가 더 작다는 것이므로 패스 해주고 1이 나온다면 더 크다는 의미이므로 path는 curPath로 대체해준다. 

여기에서 path란 distances[cur].path + 'next' 를 뜻한다.

const dikstra = (start, end, notVisites) => {
const distances = Array.from({ length: n + 1 }, () => ({
    weight: Infinity,
    path: ``,
}));

    const hq = new Heap();
    hq.push([0, start]);
    distances[start].weight = 0;
    distances[start].path = `${start}`;

    while (!hq.isEmpty()) {
        const [totalWeight, cur] = hq.pop();
        if (cur === end) break;

        for (const [next, value] of gr[cur]) {
            if (notVisites.includes(next)) continue;
            const nextTotal = totalWeight + value;

            if (distances[next].weight < nextTotal) continue;

            if (distances[next].weight === nextTotal) {
                const existPath = distances[next].path;
                const curPath = distances[cur].path + `-${next}`;
                const value = existPath.localeCompare(curPath);

                if (value === -1) continue;
                distances[next].path = curPath;
                continue;
            }
            distances[next].weight = nextTotal;
            distances[next].path = distances[cur].path + `-${next}`;
            hq.push([nextTotal, next]);
        }
    }

    return distances[end];
};

도착 지점의 path란 곧 방문했던 지점들이므로 이것을 활용하여 e에서 s로 갈때 방문하지 않을 정점의 집합으로 활용 할 수 있다.

단 s는 다시 방문해줘야 하므로 제외한다.

아래는 s에서 e로 이동하고 출발 지점을 제외한 방문하면 안되는 배열을 생성한 과정이다.

const { weight: sToEDisntance, path: visitedString } = dikstra(s, e, []);
const v = visitedString.slice(2).split('-').map(Number);

이를 활용하여 e부터 s를 이동한 뒤의 결과값을 더해주고 출력해주면 됨.

const { weight, path } = dikstra(e, s, v);

console.log(weight + sToEDisntance);

전체 코드

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 [n, m] = input[0].split(' ').map(Number);
const arr = input.slice(1, m + 1).map((s) => s.split(' ').map(Number));
const [s, e] = input[m + 1].split(' ').map(Number);
const gr = Array.from({ length: n + 1 }, () => []);
for (const [s, e, v] of arr) {
    gr[s].push([e, v]);
    gr[e].push([s, v]);
}

const dikstra = (start, end, notVisites) => {
const distances = Array.from({ length: n + 1 }, () => ({
    weight: Infinity,
    path: ``,
}));

    const hq = new Heap();
    hq.push([0, start]);
    distances[start].weight = 0;
    distances[start].path = `${start}`;

    while (!hq.isEmpty()) {
        const [totalWeight, cur] = hq.pop();
        if (cur === end) break;

        for (const [next, value] of gr[cur]) {
            if (notVisites.includes(next)) continue;
            const nextTotal = totalWeight + value;

            if (distances[next].weight < nextTotal) continue;

            if (distances[next].weight === nextTotal) {
                const existPath = distances[next].path;
                const curPath = distances[cur].path + `-${next}`;
                const value = existPath.localeCompare(curPath);

                if (value === -1) continue;
                distances[next].path = curPath;
                continue;
            }
            distances[next].weight = nextTotal;
            distances[next].path = distances[cur].path + `-${next}`;
            hq.push([nextTotal, next]);
        }
    }

    return distances[end];
};

const { weight: sToEDisntance, path: visitedString } = dikstra(s, e, []);
const v = visitedString.slice(2).split('-').map(Number);

const { weight, path } = dikstra(e, s, v);

console.log(weight + sToEDisntance);