본문 바로가기
코딩 테스트/백준

1854 K번째 최단경로 찾기(자바스크립트)

by 위그든씨 2025. 5. 16.

봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.

입력

첫째 줄에 n, m, k가 주어진다. (1≤n≤1000, 0≤m≤250000, 1≤k≤100, mk≤3000000) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1≤a,b≤n, 1≤c≤1000)

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다. 두 도로의 시작점과 도착점이 모두 같은 경우는 없다.

출력

 n개의 줄을 출력한다. i번째 줄에 1번 도시에서 i번 도시로 가는 k번째 최단경로의 소요시간을 출력한다.

경로의 소요시간은 경로 위에 있는 도로들을 따라 이동하는데 필요한 시간들의 합이다. i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 또, k번째 최단경로가 존재하지 않으면 −1을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다.

 

====

문제 풀이

다익스트라와 이진 탐색을 사용해서 문제를 해결하였다.

우선 단방향 노선들의 정보를 gr에 담아 준 뒤 힙큐를 생성하여 1번 노드에서부터 출발을 한다

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 < this.heapq.length) {
            let smallest = cur * 2;
            if (smallest >= this.heapq.length) break;

            let 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, _, k] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((s) => s.split(' ').map(Number));



const gr = Array.from({ length: n + 1 }, () => []);
const visited = Array.from({ length: n + 1 }, () => []);
for (const [s, e, v] of arr) {
    gr[s].push([e, v]);
}

const hq = new Heap();
hq.push([0, 1]);

최단 경로를 구하는 다익스트라 방식을 사용할 것인데 k번째의 최단 경로를 구하는 것이므로 기록해둘 visited는 각 노드별로 []를 할당.

기본 최단 경로 문제라면 현재에서 다음 노드 방문할 때 기록된 값보다 크다면 패스했겠지만 최대 k길이의 방문을 기록해야 한다는 것을 유의해야한다. 이때 거리 가중치를 통해 힙큐에 넣는 것을 고려한다면 1->2 로 갈때 다른 노드에서부터 1로 돌아온 뒤 다시 2로 갈때 씹히는 경우가 생긴다.  따라서 현재에서 다음 노드를 갈 수 있을지를 판단하는 것이 아닌 힙큐에서 꺼내자마자 이 최단거리 값이 visited[cur]에 기록이 가능한지로 판단한다. 현재의 distance를 visited[cur]에 이진 탐색을 통해 적절한 위치에 삽입한 후에 길이가 k+1 라면 마지막으로 제일 큰 값을 pop해주고 이것이 distance와 같다면 의미 없는 경로이므로 패스해준다. ( 삽입 전에 visited[cur].at(-1) 과 비교한 뒤에 distance가 더 크다면 그냥 패스해줘도 된다) 

위의 탐색이 끝나면 visited의 각 노드를 탐색하면서 길이가 k미만이라면 -1, k라면 마지막 값을 정답에 푸쉬해준다.

const binarySearch = (arr, value) => {
    let s = 0;
    let e = arr.length - 1;
    while (s <= e) {
        const mid = Math.floor((s + e) / 2);
        if (arr[mid] >= value) {
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return s;
};

while (!hq.isEmpty()) {
    const [distance, curNode] = hq.pop();
    const idx = binarySearch(visited[curNode], distance);
    visited[curNode].splice(idx, 0, distance);
    if (visited[curNode].length > k) {
        const value = visited[curNode].pop();
        if (value === distance) continue;
    }

    for (const [next, weight] of gr[curNode]) {
        const value = distance + weight;
        if (visited[next].length < k) {
            hq.push([value, next]);
        }
    }
}

const answer = [];
for (let i = 1; i <= n; i++) {
    if (visited[i].length < k) {
        answer.push(-1);
    } else {
        answer.push(visited[i].at(-1));
    }
}

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

정답 코드

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 < this.heapq.length) {
            let smallest = cur * 2;
            if (smallest >= this.heapq.length) break;

            let 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, _, k] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((s) => s.split(' ').map(Number));

const gr = Array.from({ length: n + 1 }, () => []);
const visited = Array.from({ length: n + 1 }, () => []);
for (const [s, e, v] of arr) {
    gr[s].push([e, v]);
}

const hq = new Heap();
hq.push([0, 1]);

const binarySearch = (arr, value) => {
    let s = 0;
    let e = arr.length - 1;
    while (s <= e) {
        const mid = Math.floor((s + e) / 2);
        if (arr[mid] >= value) {
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return s;
};

while (!hq.isEmpty()) {
    const [distance, curNode] = hq.pop();
    const idx = binarySearch(visited[curNode], distance);
    visited[curNode].splice(idx, 0, distance);
    if (visited[curNode].length > k) {
        const value = visited[curNode].pop();
        if (value === distance) continue;
    }

    for (const [next, weight] of gr[curNode]) {
        const value = distance + weight;
        if (visited[next].length < k) {
            hq.push([value, next]);
        }
    }
}

const answer = [];
for (let i = 1; i <= n; i++) {
    if (visited[i].length < k) {
        answer.push(-1);
    } else {
        answer.push(visited[i].at(-1));
    }
}

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

const binarysearch = (arr, value) => {
s = 0을하자;
e = arr.length -1을하자;
while (s <= e) {
const mid = math.floor ((s + e) ​​/ 2);
if (arr [mid]> = value) {
e = 중간 -1;
} 또 다른 {
s = mid + 1;
}
}
반환 s;
};

while (! hq.isempty ()) {
const [거리, Curnode] = HQ.pop ();
const idx = binarysearch (방문 [Curnode], 거리);
방문 된 [Curnode] .splice (idx, 0, 거리);
if (방문한 [Curnode] .length> k) {
const value = 방문 [Curnode] .pop ();
if (value === 거리) 계속;
}

for (const [next, weight] of gr [curnode]) {
const 값 = 거리 + 무게;
if (방문한 [다음] .length <k) {
HQ.push ([value, next]);
}
}
}

const 답변 = [];
for (i = 1; i <= n; i ++) {
if (방문한 [i] .length <k) {
답변 (-1);
} 또 다른 {
답변 (visited [i] .at (-1));
}
}

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

 

저작자표시 변경금지 (새창열림)

'코딩 테스트 > 백준' 카테고리의 다른 글

7453 합이 0인 네정수  (0) 2025.05.22
3151 합이 0 (자바스크립트)  (0) 2025.05.22
1800 인터넷 설치 (자바스크립트)  (0) 2025.05.15
20183 골목 대장 호석 (파이썬)  (0) 2025.05.10
1781 컵라면 (자바스크립트 / 파이썬)  (0) 2025.05.09

관련글

티스토리툴바