[백준] 13418 학교 탐방하기 (Javascript)

문제

BOJ13418_학교 탐방하기

풀이

요구사항

N개의 정점과 M개의 간선으로 이루어진 그래프가 있다.
간선은 오르막길 또는 내리막길로 구성되어 있고 이는 입력으로 주어진다.

최소한의 경로로 모든 노드를 방문했을 때, 최종적으로 지나간 $오르막길의 개수^2$ 만큼 피로도가 쌓인다.

피로도가 가장 큰 경로를 최악의 경로, 피로도가 가장 낮은 경로를 최선의 경로라고 한다.

이때, 최악의 경로에서의 피로도와 최선의 경로에서의 피로도의 차이를 구해야 한다.

출발은 무조건 입구(0번 노드)에서 출발해야 하고 입구는 1번 노드와 연결되어 있다.

또한 이미 내려갔던 길을 다시 올라갈 때는 피로도가 증가하지 않는다.

해결방안

최소한의 경로로 모든 노드를 방문해야 한다.
크루스칼 알고리즘을 사용하면 최소 신장 트리를 만들 수 있기 때문에 문제에서 요구하는 답을 구할 수 있다.
최소 신장 트리란 모든 노드가 연결되어 있고, 사이클이 발생하지 않는 트리를 말한다.
자세한 내용은 여기에 올려놨다.

다만 기존의 크루스칼 알고리즘에서는 모든 간선을 대상으로 정렬을 수행했지만, 해당 문제에서는 출발 간선이 0 -> 1 로 지정되어 있기 때문에 출발 간선은 제외하고 정렬을 수행해주어야 한다.

최선의 경로를 구할 때는 내리막길(1)이 앞에 오게 정렬하여 내리막길을 우선적으로 방문하도록 하고, 최악의 경로를 구할 때는 오르막길(0)이 앞에 오도록 정렬하여 오르막길을 우선적으로 방문하도록 하면 된다.

나머지는 기존의 크루스칼 알고리즘과 동일하다.

코드

// 오르막: 0, 내리막: 1
// 최선: 내리막 우선, 최악: 오르막 우선
// 최악일 때 피로도 - 최선일 때 피로도 구하기
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const edges = input.slice(1).map((e) => e.split(' ').map(Number));

function kruskal(edges) {
    let incline = 0;
    for (let [a, b, cost] of edges) {
        if (find(a) !== find(b)) {
            union(a, b);
            // 오르막 개수
            if (cost === 0) incline++;
        }
    }
    return incline ** 2;
}

function union(a, b) {
    a = find(a);
    b = find(b);
    if (a < b) parents[b] = a;
    else parents[a] = b;
}

function find(x) {
    if (parents[x] !== x) parents[x] = find(parents[x]);
    return parents[x];
}

// 최적의 경로 구하기
edges.sort((a, b) => {
    if (b[0] === 0) return 0;
    else return b[2] - a[2];
});
let parents = Array.from({ length: N + 1 }, (_, i) => i);
const best = kruskal(edges);

// 최악의 경로 구하기 (내림차순 정렬)
edges.sort((a, b) => {
    if (b[0] === 0) return 0;
    else return a[2] - b[2];
});
parents = Array.from({ length: N + 1 }, (_, i) => i);
const worst = kruskal(edges);

console.log(worst - best);